[프로그래머스 Programmers][Python] 등굣길

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

코딩테스트 연습 - 등굣길 | 프로그래머스

이 문제는 DP에서 전형적으로 나오는 최단경로 문제이다.

복잡한 조건이 없는 최단경로 개수는 방식이 정해져 있다.

 

1. 우선 최단경로로 갈 수 있는 방법을 생각한다.
   1. 이 문제의 경우 오른쪽, 아래 2가지 경우뿐이다.
   2.  d[i][j] = (d[i-1][j] + d[i][j-1])
2. 각 길에 대한 가중치 같은 것이 있나 확인한다.
   1. 이 문제는 없다. 있을 시 max 등을 확인해서 계산할 것
3. 맵에 대한 초기화를 실행한다.
   
   1. 길 찾기 문제 중에 d[1][i] = sth 이 값을 초기 설정해줘야 하는 경우가 있다.
   2. 지금은 아님.
4. 못 가는 길을 확인한다.
   1. 이 경우는 puddles 잠긴 지역이 있으니, for 문을 돌며 갈 수 없는 길일 경우 0 처리한다.
   2. if ~else 구문이 조건 처리 코드이다.

 

 

def solution(m, n, puddles):
    answer = 0
    d = [[0]*(m+1) for _ in range(n+1)]
    
    d[1][0] = 1

    for i in range(1,n+1):
        for j in range(1,m+1):

            if [j,i] in puddles:
                d[i][j] = 0
            else:
                d[i][j] = (d[i-1][j]+d[i][j-1])%1000000007  


    return d[n][m]