[알고리즘] 백준 1520 내리막길

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

처음에는 보고 전형적인 2차원 리스트를 이용한 DFS 문제라고 생각하였다. 각 경로를 지나가며 현재 칸의 높이와 다음 높이를 비교하여 현재 칸보다 다음 칸의 높이가 낮다면, 다음 재귀 함수를 호출해주는 식으로 구현하였다.

실패코드

import sys

M, N = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
visited = [[False for _ in range(N)] for _ in range(M)]

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

result = 0
def dfs(x, y, now):
    global result

    if x == M-1 and y == N-1:
        result += 1
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N and not visited[nx][ny]:
        	# 현재 높이와 다음 높이를 비교해서 낮으면 다음 경로 탐색 진행
            if board[nx][ny] < now:
                visited[nx][ny] = True
                dfs(nx, ny, board[nx][ny])
                visited[nx][ny] = False

visited[0][0] = True
dfs(0, 0, board[0][0])
print(result)

그러나 문제에서 주어진 M과 N의 최대값이 500이다보니, 500 * 500 = 250000의 최대 크기에서 위 코드처럼 모든 경로를 다시 방문하도록 구현하면 시간 초과가 발생하게 된다. 위 코드는 16%까지 진행되고 시간 초과를 받았다..(PyPy로도 무용지물..)

이를 개선하기 위해서는 DP와 DFS를 조합하여 한번 이동했던 경로에 대해서는 memoization을 이용하여 재 탐색을 하지 않도록 할 수 있다. 아래는 시간 초과를 개선하여 AC를 받은 코드이다.

성공 코드

import sys

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

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# memoization 리스트 값 -1로 초기화 ( -1은 아직 방문하지 않은 상태라는 의미 )
# dp[x][y] 는 x, y에서 도달할 수 있는 경로의 값을 의미한다.
dp = [[-1 for _ in range(N)] for _ in range(M)]

result = 0
def dfs(x, y):
    global result

	# 도착지점에 도달할 경우, 유효 경로에 해당되므로 1을 return 시켜
    # 현재까지 걸어온 모든 좌표들에 1씩을 더해준다.
    if x == M-1 and y == N-1:
        return 1
	
    # 한번도 방문한적 없는 위치라면 방문 체크하고 탐색 진행
    if dp[x][y] == -1:
        dp[x][y] = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if board[x][y] > board[nx][ny]:
                	# 0으로 초기화 시켜 주었고, 만약 도착지에 도달할 경우 1씩 더해주기 때문에,
                    # 값이 1인 좌표들은 경로에 해당하는 좌표이며, 그대로 0인 좌표들은 해당 경로로는
                    # 목표지점에 도달할 수 있는 좌표임을 의미한다.
                    dp[x][y] += dfs(nx, ny)
    # 방문한적 있다면, 해당 위치의 memoization 값을 반환한다.
    return dp[x][y]

print(dfs(0, 0))