[Python] 백준 / Gold / 1520 : 내리막길 ( DFS + DP )

문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

2가지 해법으로 이 문제를 풀어보았다.

 (1) 도착점에서 출발점으로 깊이 우선 탐색 (DFS)

 (2) 출발점에서 도착점으로 DFS

 

1번 풀이에서의 dp[x][y] == (x, y)에서 (0, 0) 까지 갈 수 있는 경로의 개수

2번 풀이에서의 dp[x][y] == (x, y)에서 (N-1, M-1) 까지 갈 수 있는 경로의 개수

 

😊 풀이 1 : 도착점부터 출발점까지 거슬러 올라가는 방법

# 뒤에서부터 앞으로 DFS + DP 진행

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

visited = [[False] * M for _ in range(N)]
dp = [[-1] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(x, y):
    if x == 0 and y == 0:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]

            if 0 <= nx < N and 0 <= ny < M and graph[x][y] < graph[nx][ny]:
                dp[x][y] += dfs(nx, ny)

    return dp[x][y]

print(dfs(N-1,M-1))

풀이 1 - 참고용 dp table 출력

😊 풀이 2 : 출발점부터 도착점까지 따라 내려가는 방법

# 앞에서부터 뒤로
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

visited = [[False] * M for _ in range(N)]
dp = [[-1] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(x, y):
    if x == N-1 and y == M-1:
        return 1
    if dp[x][y] != -1:
    	return dp[x][y]
    else:
        dp[x][y] = 0
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]

            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] < graph[x][y]:
                dp[x][y] += dfs(nx, ny)

    return dp[x][y]

print(dfs(0, 0))

풀이 2 - 참고용 dp table 출력

 

🙄 문제를 통해 얻어가는 것 3가지 

1. DFS에서 visited 처리를 했을 때와 안했을 때의 차이

이 문제에서 방문처리를 하며 DFS를 진행하면 모든 경로를 구할 수 없다.

[그림 1]

[그림1]과 같이 빨간색 경로로 탐색이 진행된 후에, 파란색 경로로 탐색을 진행하려고 하면, 이미 빨간색 경로에서 visited 처리된 노드가 있기 때문에 끝까지 탐색을 진행할 수 없다.

 

이 문제에서는 계속해서 높이가 낮은 경로를 찾아 탐색하기 때문에 방문 처리를 하지 않아도 뒤로 다시 돌아가는 일이 없이 모든 경로를 찾아낼 수 있다.

 

2. 일반적인 DFS와 Dynamic Programming을 활용한 DFS의 시간복잡도 차이

문제의 input 조건

M, N이 최대 500 이기 때문에 일반적인 DFS를 진행하면 4방향 ^ ( 500 * 500 )의 연산으로 효율성이 낮다.

따라서 중복되는 연산을 반드시 제거해야 효율성 테스트를 통과할 수 있다.

 

3. DFS + DP의 조합으로, 중복 경로 연산을 제거 할 수 있음

Dynamic Programming을 사용하여 불필요한 중복을 줄일 수 있었다.