[BOJ 1520] DP와 그래프탐색을 함께 사용해야 하는 케이스

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

1520번: 내리막 길

간단해 보이는 문제이지만 DP와 그래프탐색, 그리고 그 둘을 함께 사용하는 방식에 익숙하지 않다면 깔끔하게 풀어내지 못할 수 있다.

제일 왼쪽 위 지점에서 제일 오른쪽 아래 지점으로 가는 경로의 개수를 구하는 것이 목표이고, 최초로 떠올린 알고리즘은 DP였다.

하지만 이 문제는 점화식을 바탕으로 단순히 DP 행렬을 구축할 수 없다.

이후 DFS로 문제를 해결하고자 하였다. 결국 오른쪽 아래까지 갈 수 있는 경로를 세어야 하므로 가능한 경로를 모두 탐색해야 한다고 판단하였다.

물론 가능한 경로를 모두 고려해야 하지만 DFS를 사용할 경우 동일한 경로를 여러번 연산하게 된다.

예시의 경로 3개 중 두번째와 세번째의 경우 20->17->15->10 부분이 동일하다. 하지만 단순히 DFS를 적용하면 이 부분이 여러번 연산될 것이다.

 

단순한 DP로 풀기엔 다양한 경로를 탐색해야하고

DFS만으로 풀기엔 동일한 연산을 여러번 하게 된다.

 

따라서 DP를 점화식이 아닌 그래프 탐색 기반으로 활용하여 코드를 설계해야 한다.

r행 c열에 저장되는 값은 r행 c열 부터 도착지까지 가는 경로의 수이다.

r행 c열은 인접한 네 개의 칸 중 r행 c열에 적힌 수보다 작은 수가 적힌 칸의 DP값을 모두 더한 수를 저장하면 된다.

이때 만약 DP값이 미리 계산되어 있지 않다면 재귀함수를 통해 그 칸을 먼저 계산하도록 프로그래밍한다.

이를 위해선 각 칸이 계산이 되었는지 되지 않았는지 판단할 수 있어야 하므로 최초에 DP 테이블을 -1로 초기화한다.

DP 테이블의 값들을 계산하는 과정에서 참조한 DP값이 -1이면 그 값을 먼저 계산하는 방식으로 재귀적으로 알고리즘을 설계하면 DP테이블이 이쁘게 만들어진다.

 

소스코드

import sys
sys.setrecursionlimit(10**6)

INF = int(1e9)


def FastInput():
    return sys.stdin.readline().rstrip()

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

height_table = [[INF for i in range(N+2)]]
for m in range(M):
    height_table.append([INF] + list(map(int, FastInput().split())) + [INF])
height_table.append([INF for i in range(N+2)])

DP = [[-1 for i in range(N+2)] for j in range(M+2)]


def DFS(cur_r, cur_c):
    global height_table, DP
    DP[cur_r][cur_c] = 0
    if cur_r == M and cur_c == N:#here is arrival
        DP[cur_r][cur_c] = 1
        return
    
    dr_and_dc = [(0,1),(0,-1),(1,0),(-1,0)]
    for dr, dc in dr_and_dc:
        if height_table[cur_r][cur_c] <= height_table[cur_r+dr][cur_c+dc]: continue
        if DP[cur_r+dr][cur_c+dc] == -1:
            DFS(cur_r+dr, cur_c+dc)
        DP[cur_r][cur_c] += DP[cur_r+dr][cur_c+dc]

DFS(1, 1)
print(DP[1][1])

 

이렇듯 점화식을 바탕으로 반복문(혹은 이중반복문)을 통해 DP테이블을 구축하는 것이 아니라, 그래프 탐색을 하듯 재귀적으로(혹은 queue를 활용하여) DP테이블을 구축하는 문제는 처음 풀어보았다.

다음에 유사한 문제가 나오면 꼭 해치우도록 하자!