[백준 파이썬] 1520 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

 

문제



주어진 2차원 배열에서 내리막으로만 갈 수 있는 길의 경우의 수를 계산하는 문제이다.

---

풀이

가장 먼저 떠오른 방법은 DFS를 이용하여 경로를 찾는 것이었다.

하지만 DFS를 단독으로 사용하면 수많은 경로를 모두 탐색해야 하기 때문에 시간초과가 발생한다.

따라서 DP와 DFS를 같이 사용해야한다.

 

graph = [list(map(int, input().split())) for _ in range(M)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dp = [[-1] * N for _ in range(M)]

먼저 그래프를 입력받고 해당 그래프와 같은 크기에 DP를 생성한다.

 

DFS는 다음과 같이 구현된다.

if sx == M -1 and sy == N - 1:
        return 1
    
if dp[sx][sy] != -1:
    return dp[sx][sy]

만약 이동된 좌표가 마지막 좌표일 경우 1 (갈 수 있는 방법이 하나 추가됨)을 반환한다.

 

또는 이동된 좌표의 DP값이 -1이 아닌경우 (이미 해당 좌표에서 갈 수 있는 경로를 탐색함) 해당 좌표의 DP값을 반환한다.

 

 ways = 0
    for i in range(4):
        nx = sx + dx[i]
        ny = sy + dy[i]
        
        if 0 <= nx < M and 0 <= ny < N and graph[sx][sy] > graph[nx][ny]:
            ways += DFS(nx, ny)

두 경우에 해당되지 않을경우 DFS를 사용하여 탐색한다.

이동된 좌표가 그래프의 범위를 넘지 않고 현재 위치보다 낮을 경우

다음 DFS의 반환값을 ways값에 더한다.

 

dp[sx][sy] = ways
return dp[sx][sy]

모두 더한 ways값은 DP의 현재 좌표에 할당한다.

이 후 dp의 현재좌표 (현재 좌표에서 이동할 수 있는 경우의 수)를 반환한다.

 

 

 

 

코드

 M, N = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(M)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dp = [[-1] * N for _ in range(M)]

def DFS(sx, sy):
    if sx == M -1 and sy == N - 1:
        return 1
    
    if dp[sx][sy] != -1:
        return dp[sx][sy]
    
    ways = 0
    for i in range(4):
        nx = sx + dx[i]
        ny = sy + dy[i]
        
        if 0 <= nx < M and 0 <= ny < N and graph[sx][sy] > graph[nx][ny]:
            ways += DFS(nx, ny)
    
    dp[sx][sy] = ways
    return dp[sx][sy]


DFS(0, 0)
print(DFS(0, 0))