[Programmers_Python] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

이 문제는 DP로 풀어야하는 문제인데 DP문제를 최근에 많이 안풀어 봐서 그런지 처음에 어떻게 해야할지 감을 제대로 못잡았었다. 그래서 다른 분들의 블로그를 참고했다.

푸는 방법은 각 지점까지 갈 수 있는 최단 경로의 개수를 각 지점에 저장해 두는 것이다. 문제의 그림에 직접 표시해보면 아래와 같은 그림이 나온다.

 

문제에서 나왔듯이 아래 혹은 오른쪽으로만 이동할 수 있기에 아래와 같은 점화식으로 표현할 수 있다.

위 점화식을 아래와 같이 코드로 나타낼 수 있다.

for i in range(n):
	for j in range(m):
    	if road[i][j] == 0:
        	pass
       	else:
        	if i-1 >= 0 and j-1 >= 0:
            	road[i][j] = road[i-1][j] + road[i][j-1]
            elif i-1 >= 0 and j-1 < 0:
            	road[i][j] = road[i-1][j]
            elif i-1 < 0 and j-1 >= 0:
            	road[i][j] = road[i][j-1]

조심해야할 부분은 물에 잠긴 지점은 계산되면 안된다는 것과 물에 잠긴 지점의 좌표가 [p,q]면 [q,p]로 리스트에서 나타내야한다는 것이다.

for lst in puddles:
	x = lst[0]
    y = lst[1]
    road[y-1][x-1] = 0

조심해야할 부분을 위와 같은 방식으로 나타냈다.

아래의 코드는 완성된 부분의 코드이다.

def solution(m, n, puddles):
    road = []
    for i in range(n):
        road.append([1]*m)
    for lst in puddles:
        x = lst[0]
        y = lst[1]
        road[y-1][x-1] = 0
    for i in range(n):
        for j in range(m):
            if road[i][j] == 0:
                pass
            else:
                if i-1 >= 0 and j-1 >= 0:
                    road[i][j] = road[i-1][j] + road[i][j-1]
                elif i-1 >= 0 and j-1 < 0:
                    road[i][j] = road[i-1][j]
                elif i-1 < 0 and j-1 >= 0:
                    road[i][j] = road[i][j-1]       
    return road[n-1][m-1]%1000000007

시험기간동안 코테 문제들을 안풀다가 오랜만에 풀었는데 감이 많이 떨어진 것 같았다.... 특히 DP는 원래도 잘 못했었는데 오랜만에 푸니까 처음 접근 방식부터 막혔던 것 같다. 이제 종강도 했으니 다시 꾸준히 열심히 해야겠다는 생각이 들었다ㅎㅎ