[프로그래머스 42898 파이썬] 등굣길 (level 3, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=python3

소스 코드(파이썬)

import sys
from collections import deque
input = sys.stdin.readline

def move(x, y):
    yield x+1, y
    yield x, y+1

# (x, y)에서 (m, n)으로의 최단 경로 개수 리턴
def DFS(x, y, n, m, DP):
    if (x, y) == (n-1, m-1):
        return 1
    
    # 이미 값이 구해져있으면 바로 리턴
    if DP[x][y] != -1:
        return DP[x][y]
    
    # 아래와 오른쪽 좌표의 최단 경로 개수 더한 것이
    # 현재 좌표에서의 최단 경로 개수
    dist = 0
    for adj_x, adj_y in move(x, y):
        if not(0 <= adj_x < n and 0 <= adj_y < m):
            continue
        
        dist += DFS(adj_x, adj_y, n, m, DP)
    
    DP[x][y] = dist % 1000000007
    return dist % 1000000007

def solution(m, n, puddles):
    # -1이면 아직 경로 개수가 구해지지 않은 좌표
    DP = [[-1]*m for _ in range(n)]
    
    # 물 웅덩이에서 목적지로 가는 경로 개수는 0개
    for x, y in puddles:
        DP[y-1][x-1] = 0
    
    return DFS(0, 0, n, m, DP)

print(solution(4, 3, [[2,2]]))

풀이 요약

1. DP를 활용한 그래프 탐색 문제이다.

   출발 좌표로부터 DFS를 돈다. DFS의 리턴 값은 현재 좌표로부터 목적 좌표까지의 최단 경로 개수이다.

   따라서 DFS의 종료 조건은 목적 좌표일때이고, 1을 리턴해준다.

   인접 좌표로 탐색을 하기에 앞서, 해당 탐색에는 DP 개념을 적용할 수 있다.

   어떤 좌표에서 목적 좌표까지의 최단 경로 개수는, 아래 좌표와 오른쪽 좌표의 최단 경로 개수의 합과 같다.

   이를 DFS로 재귀적으로 구해나가면서, DFS 값이 확정되는 좌표에서는 DFS 값을 리턴하기 직전에 DP 리스트에 따로 값을 저장해둔다.

   그리고 다른 갈래에서의 탐색에서, 좌표를 재방문할 때 앞서 저장해 둔 DP 값을 활용할 수 있다.

2. 이 문제의 경우 행열을 거꾸로 줘서 m이 열, n이 행을 의미하는데 이를 고려하면서 풀자.

배운 점, 어려웠던 점

• 풀어봤던 문제 유형인데 DFS 리턴 값을 잘못 정의해서 계속 해맸다.. 앞으로 똑같은 실수를 하지 않도록 노력하자.