[프로그래머스_42898] 등굣길 Python 풀이

출처: 프로그래머스

문제

풀이

동적계획법으로 풀어주었습니다.

일단 움직일 수 있는 범위가 오른쪽과 아래쪽밖에 없으므로 돌아가는 경우는 생각해주지 않아도 되기 때문에 모든 경로가 최단거리가 됩니다.

우선 n * m 크기의 graph를 만들어주고, 1로 초기화해주었습니다.

그 뒤, 침수 지역은 0으로 표시하고, 아래로만 가는 경우와, 오른쪽으로만 가는 경우를 초기화해주었습니다. 만약 아래로만 가는 경로와, 오른쪽으로만 가는 경로에 침수 지역이 있다면 더 이상 갈 수 없기 때문에, 이전 지역이 0이라면 다음 지역도 0이 되게끔 해주었습니다.

위에서 예외처리해준 부분을 제외하고 모든 지역은 각각 왼쪽, 위쪽에서 오는 경우만 해당 좌표에 도달할 수 있으므로 두 가지의 경로를 더해준 값에서 1,000,000,007으로 나눈 값을 저장해줍니다.

마지막에는 학교의 좌표에 저장된 값을 return 해줍니다.

코드

def solution(m, n, puddles):
    # 모든 지역 1로 초기화
    graph = [[1 for _ in range(m)] for _ in range(n)]
    # 침수 지역 표시
    for px, py in puddles:
        graph[py-1][px-1] = 0
    # 아래로만 가능 경우 초기화
    # 침수 지역을 만나게 되면 더이상 아래로 갈 수 없다.
    for i in range(1, n):
        if graph[i-1][0] == 0:
            graph[i][0] = 0
    # 오른쪽으로만 가능 경우 초기화
    # 침수 지역을 만나게 되면 더이상 오른쪽으로 갈 수 없다.
    for j in range(1, m):
        if graph[0][j-1] == 0:
            graph[0][j] = 0
    # 각각 왼쪽, 위의 방향에서 오는 경우만 해당 좌표에 도달할 수 있다.
    for y in range(1, n):
        for x in range(1, m):
            if graph[y][x] == 0:
                continue
            graph[y][x] = (graph[y-1][x] + graph[y][x-1]) % 1000000007
    return graph[n-1][m-1]