[백준 1520번] 내리막 길

import sys
sys.setrecursionlimit(50000000);

m, n = map(int,input().split())
area = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)]
nx, ny = [-1,1,0,0], [0,0,-1,1]

def dfs(x,y):
    
    # 도착 지점에 도달하면 1 리턴
    if x == (m-1) and y == (n-1):
        return 1
    # 이미 방문한 길이라면 경우의 수를 구하지 않고 해당 위치에서 출발하는 경우의 수 리턴
    if dp[x][y] != -1:
        return dp[x][y]
    
    way_count = 0

    for i in range(4):
        temp_x = x + nx[i]
        temp_y = y + ny[i]

        if temp_x >= 0 and temp_x < m and temp_y >= 0 and temp_y < n and area[temp_x][temp_y] < area[x][y]:
                way_count += dfs(temp_x,temp_y)
    
    dp[x][y] = way_count

    return dp[x][y]

print(dfs(0,0))

이번 문제는 각 좌표에 높이가 저장된 2차원 리스트가 주어지고, (0,0)에서 시작하여 (m-1,n-1) 지점까지 이동하되, 현재 위치보다 높이가 낮은 좌표로만 이동할 때 마지막 좌표까지 이동할 수 있는 경우의 수를 구하는 문제이다.

 

import sys
sys.setrecursionlimit(50000000);

m, n = map(int,input().split())

area = [[] for _ in range(m)]
visited = [[False]*n for _ in range(m)]

count = 0

for i in range(m):
    area[i] = list(map(int,input().split()))

def dfs(x,y):

    global count
    global visited

    if visited[x][y]:
        return False
    
    if x == (m-1) and y == (n-1):
        count += 1
    
    visited[x][y] = True

    nx = [-1,1,0,0]
    ny = [0,0,-1,1]

    for i in range(4):
        temp_x = x + nx[i]
        temp_y = y + ny[i]

        if temp_x >= 0 and temp_x < m and temp_y >= 0 and temp_y < n:
            if area[temp_x][temp_y] < area[x][y]:
                dfs(temp_x,temp_y)

    visited[x][y] = False

dfs(0,0)

print(count)

처음에 이 문제를 풀었을 때는 DFS를 사용해서 (m-1, n-1) 지점에 도착했을 경우 경우의 수(count)를 1 올려주는 위와 같은 방식으로 풀이를 하였다.

하지만 13% 에서 시간초과가 발생했고, 그 이유를 생각해보니 DFS만으로 풀이를 하게 되면 500 * 500 배열에서 상하좌우로 4가지 연산을 진행하게 되면 어마어마한 경우의 수를 계산하게 된다.

 

이 문제의 경우 시작, 도착점이 아닌 임의의 지점(a,b)에서 도착지점 (m-1, n-1) 까지 가는 경우의 수가 구해지면, 그 이전의 어떤 경로로 (a,b)에 도착하기만 하면 그 때부터의 경우의 수는 다시 구할 필요가 없다.

 

다시 말해서, 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같아진다는 것이다.

 

따라서 DP를 사용하여 불필요한 연산을 줄여주어야 하는데, 다른 사람의 풀이를 보기전에도 이미 방문하여 마지막 지점까지의 경로의 수를 구한 지점을 DP테이블에 저장하여 풀어야 한다는 것은 인지하였지만 어떤 방식으로 메모이제이션을 해주어야 할지 잘 떠오르지 않았다.

 

다른 사람의 풀이를 참고해본 결과, 이 문제의 DP 방식에 핵심은 다음과 같다.

시작 지점(0,0)에서 출발해서 DP 테이블이 갱신되지 않은 곳(-1)을 만난다면, 해당 지점부터 도착 지점까지 갈 수 있는 경로의 수(way_count)를 DP 테이블에 업데이트 한다. 해당 지점의 DP 테이블이 이미 갱신되어 있다면 그 곳이 위에서 말한 부분 최적해가 되므로 그 값을 그대로 전체 정답에 더해주면 된다.

 

DFS나 BFS로 풀이하였을 때 시간초과가 발생하였을 때는 불필요한 연산을 줄이기 위해 DP를 사용해야 하는데, 이를 위해 메모이제이션 하는 방식을 떠올리는 것이 중요하다는 것을 깨달았을 뿐만 아니라, 코드를 깔끔하게 작성할 수 있는 방식(2차원 배열 선언과 동시에 입력받기, nx/ny) 또한 배울 수 있었던 좋은 문제였다 :)