[BOJ] 1520번 내리막 길

백준 1520번 내리막 길 (골드 3)

문제

문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

문제 풀이

보통 BFS/DFS에서는 방문 처리를 하여 다시 방문하지 않도록 하는데 이 문제에서는 그럴 필요가 없었다.
왜냐하면 숫자가 더 작은 곳으로 이동하는 것이기 때문에 되돌아가는 경우가 없을 뿐더러 여러 경로를 구할 때 중복된 위치를 이동할 수 있어야 하기 때문이다.

하지만 중복된 위치를 지나가는데 매번 탐색해야 한다면 비효율적일 수 있다. (처음에 항상 탐색하도록 짰다가 시간 초과를 보았다)

해결법은 이 문제에 Dynamic Programming을 접목할 수 있다는 것이다.

1. (x,y)에서 (n-1, m-1)까지 가는 내리막 길 수를 한 번 구했다면 이후엔 DP 테이블에 저장한다.

2. 만약 다른 길을 통해서 (n-1, m-1)위치에 도달하면, DP 테이블에 저장된 값을 바로 돌려주면 되기 때문에 불필요한 중복 탐색을 방지할 수 있다.

import sys


def dfs(x, y):
    global answer
    if (x, y) == (n - 1, m - 1):
        return 1
    if dp[x][y] != -1:
        return dp[x][y]

    count = 0
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] < graph[x][y]:
            count += dfs(nx, ny)

    dp[x][y] = count
    return dp[x][y]

if __name__ == "__main__":
    sys.setrecursionlimit(10**4)
    input = sys.stdin.readline

    n, m = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    answer = 0
    dp = [[-1] * m for _ in range(n)]
    
    print(dfs(0, 0))
    
    # for i in range(n):
    #     print(dp[i])