- Problem Link : https://www.acmicpc.net/problem/1520
문제
세준이는 높이가 더 낮은 지점으로만 이동할 수 있을때 오른쪽 아래 지점까지 이동하는 경로의 개수를 구하여라.
입력
- 첫째 줄, 지도의 세로 크기 M, 가로 크기 N이 주어진다.
- 다음 M개의 줄에 걸쳐 한 줄에 N개씩 위에서부터 주어진다.
출력
- 첫째 줄, 이동 가능한 경로의 수 H를 출력한다.
풀이
이 문제는 DFS 문제로 해결할 수 있다. 중요한 점은 DFS 방식과 DP 방식을 함께 사용해서 해결해야한다는 점이다. 기존의 DFS는 목표지점에 도달할 수 있는지 없는지를 판단하는데 주로 사용했지만 이 문제의 경우 도달할 수 있는 모든 경우를 세야하기 때문에 도달했다고 프로그램을 종료하면 안 되고 계속해서 확인을 해야한다.
그렇다고 이 문제를 DFS 재귀를 계속 진행하면서 모든 경로에 도달하는 경우를 확인하면 지도의 크기가 커지면 초과가 발생한다. 따라서 시작 지점에서 모든 경로를 DFS로 해보는 것이 아니라. 도착점에 도착하면 1을 리턴받으면서 올라오면서 DP 배열에 저장하면서 진행해야 한다. 즉, DP 리스트에는 도착 지점까지 갈 수 있는 방법의 수가 정해진다고 생각하면 된다. 아래 예시를 참고하면 이해하기 쉽다.
예시
기존 DFS 방식으로 경로를 모두 찾으면 갈래가 퍼질 때마다 경로가 추가되면서 똑같은 경로를 두 세번 지나가게 되는 것을 확인할 수 있다. 이렇게 되면 입력이 커지면 커질 수록 시간 초과가 발생할 수 밖에 없다. 따라서 중복된 경로를 지나가지 않기 위해 위에서 설명했던데로 도착점에 도달하면 리턴을 받으면서 해당 리턴 값을 DP 리스트에 더해주면서 시작점으로 올라오는 방식으로 구현한다. 이렇게 하면 결국 리턴 값이 반환될 때까지 기다리므로 결국 모든 경로를 확인하면서 올라갈 수 있다. 아래 그림을 참고하자.
도착점에 도달하면 1을 리턴받으면서 반대 방향으로 올라오기 시작한다. 아래 코드를 보면 dfs(ni, nj)를 cnt에 더하면서 진행한다. 이렇게 코딩하면 dfs의 값을 리턴 받을 때까지 기다리기 때문에 경로를 순차적으로 방문하도록 구현이 가능하다. 위 그림에서 각각의 경로를 순서대로 확인한다. 이 때 중요한 점은 dp에 -1이 아닌 값이 들어있으면 더 이상 경로를 따라가지 않고 그 dp 값을 그대로 return 시켜버리는 것이다. 그 이유는 해당 경로에 dp 값이 들어가 있다는 것은 이전의 다른 경로가 이미 그 칸을 지나서 도착점에 도달한 후에 리턴 받아서 돌아오면서 dp를 채웠음을 의미한다. 그러므로 지금의 경로 또한 이 칸에 도착해서 도착점에 갈 수 있다는 것을 의미하고 굳이 또다시 도착점까지 갈필요가 없다. 따라서 해당 칸을 지나는 dp 값을 그대로 반환 받아서 return 시키면 된다. 아래 그림을 참고하자.
도착점에 도달한 경로는 무조건 1을 반환 받는다. 그 1이 온 경로를 따라가면서 dp에 해당 값을 넣으면서 돌아간다. 그렇게 되면 2개의 경로가 만나게 되는데 이 때 cnt += dfs(ni, nj) 이 부분에서 같은 칸으로 반환되어온 경로의 dp 값을 모두 더하게 된다. 따라서 그림의 (0, 3)에서 올라온 1 두 개가 합쳐서 2로 dp 값이 추가된다. 이제 이 2가 다시 경로를 따라서 올라간다. 그러다가 (0, 0)에서 1, 2가 만나는데 여기서도 (0, 3)과 동일하게 모든 경로의 dp 값의 합이 더해지면서 최종 결과 3이 만들어진다.
이 문제는 기존의 DFS 방식과는 다르게 DP를 이용해 해당 칸부터 도착점까지 갈 수 있는 경우의 수를 Top-Down 방식으로 업데이트 하면서 시작점까지 돌아오는 방식으로 해결할 수 있다.
위와 같은 방식으로 동일한 경로를 여러번 지나는 케이스를 제거할 수 있고 이를 이용해 실행 시간을 단축시킬 수 있다.
코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
# dfs
def dfs(i, j) :
if i == m-1 and j== n-1 :
return 1
if dp[i][j] != -1 :
return dp[i][j]
cnt = 0
for d in range(4) :
ni = i + di[d]
nj = j + dj[d]
if 0 <= ni < m and 0 <= nj < n and graph[ni][nj] < graph[i][j] :
cnt += dfs(ni, nj)
dp[i][j] = cnt
return dp[i][j]
# input
m, n = map(int, input().rstrip().split())
graph = [list(map(int,input().rstrip().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
print(dfs(0, 0))