[프로그래머스] 등굣길

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

일부 못가는 구간이 있을 때 가장 빨리 갈 수 있는 최단경로의 개수를 구하는 문제이다.

단순히 가장 빨리 가는 코스를 찾으라고 했으면 BFS로 풀었겠지만 모든 경우를 탐색해야하기에 DP로 접근해야하는 문제였다.

def solution(m, n, puddles):
    answer = 0
    puddles = set((x-1, y-1) for x, y in puddles)
    
    dp = [[-1] * m for _ in range(n)]
    
    dy = [0, 1]
    dx = [1, 0]
    
    dp[n-1][m-1] = 1

    
    def dfs(y, x):
        if dp[y][x] != -1:
            return dp[y][x] % 1000000007
        
        dp[y][x] += 1
        
        for d in range(2):
            ny = y + dy[d]
            nx = x + dx[d]
            
            if 0 <= ny < n and 0 <= nx < m and (nx, ny) not in puddles and y <= ny and x <= nx:
                dp[y][x] += (dfs(ny, nx) % 1000000007 )
        
        return dp[y][x]
    
    return dfs(0, 0) % 1000000007 

먼저 못가는 지역을 set으로 바꾸어서 어떤 좌표가 못가는 구역에 있는지 확인할 때 O(1)의 시간이 걸리도록 했다.

방향은 집이 가장 왼쪽위에 있고 학교가 가장 오른쪽 아래에 있기에 오른쪽과 아래쪽으로 가는 방향만 설정했다.

DP를 저장할 2차원 배열을 만들고, DFS로 탐색을 시작했다.

DFS에서는 만약 어떤 좌표 [y, x]가 이미 방문했다면 해당 위치의 값을 반환했고, 그렇지 않다면 0으로 초기화 해준 뒤 오른쪽과 아래쪽 점이 탐색 가능하다면 해당 점에 대해서 다시 DFS를 실행하고 그 결과를 df[y][x]에 더해주었다.

시작은 0, 0부터 시작했지만 stack처럼 맨 오른쪽 아래 점부터 시작해서 그 결과가 저장되어서 0, 0에 저장되는 방식이 되었다.

나중에 자바로 다시 풀어봐야겠다.