1520🐨내리막 길-동적 프로그래밍

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

알고리즘 설명: DFS와 동적 프로그래밍을 사용한 경로 수 계산

이 글에서는 주어진 그리드에서 출발점(0, 0)에서 도착점(M-1, N-1)까지의 경로 수를 계산하는 알고리즘을 설명한다. 이 알고리즘은 DFS(깊이 우선 탐색)와 동적 프로그래밍을 결합하여 효율적으로 모든 가능한 경로를 탐색하고 경로 수를 계산한다.

1. 코드 개요

다음은 전체 코드이다. 이를 부분적으로 나누어 설명하겠다.

import sys
sys.setrecursionlimit(10**6)

def count_paths(M, N, grid):
    dp = [[-1] * N for _ in range(M)]    # dp 배열 초기화

    def dfs(x, y):
        if x == M - 1 and y == N - 1:
            return 1 # 도착점에 도달하면 1 반환
        if dp[x][y] != -1:
            return dp[x][y] # 이미 계산된 경우 dp 배열 반환
        dp[x][y] = 0 # 초기화
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # 네 방향으로 이동
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] < grid[x][y]:
                dp[x][y] += dfs(nx, ny)
        return dp[x][y]

    return dfs(0, 0)

m, n, *arr = map(int, sys.stdin.read().split())
it = iter(arr)
grid = [[next(it) for _ in range(n)] for _ in range(m)]
print(count_paths(m, n, grid))

2. 재귀 깊이 설정

import sys
sys.setrecursionlimit(10**6)

• sys.setrecursionlimit(10**6)은 재귀 호출의 최대 깊이를 1,000,000으로 설정한다. 이는 깊이 우선 탐색을 수행할 때 재귀 호출이 깊어질 수 있으므로, 기본 재귀 깊이 제한을 늘려 에러를 방지하기 위해 사용된다.

3. count_paths 함수

def count_paths(M, N, grid):
    dp = [[-1] * N for _ in range(M)]    # dp 배열 초기화

• count_paths 함수는 M x N 크기의 그리드를 입력받아 출발점에서 도착점까지의 경로 수를 계산하는 함수이다.
• dp 배열은 각 위치에서 도착점까지의 경로 수를 저장하기 위해 사용된다. 처음에는 모두 -1로 초기화되어, 아직 계산되지 않았음을 나타낸다.

4. DFS(깊이 우선 탐색) 함수

    def dfs(x, y):
        if x == M - 1 and y == N - 1:
            return 1 # 도착점에 도달하면 1 반환
        if dp[x][y] != -1:
            return dp[x][y] # 이미 계산된 경우 dp 배열 반환
        dp[x][y] = 0 # 초기화
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # 네 방향으로 이동
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] < grid[x][y]:
                dp[x][y] += dfs(nx, ny)
        return dp[x][y]

• dfs 함수는 현재 위치 (x, y)에서 도착점까지의 경로 수를 계산한다.
• (x, y)가 도착점 (M-1, N-1)일 경우 1을 반환하여 경로의 끝임을 알린다.
• 이미 계산된 경로 수가 dp 배열에 저장되어 있다면, 해당 값을 반환한다.
• 현재 위치에서 네 방향(상, 하, 좌, 우)으로 이동하며, 이동할 위치가 그리드 내에 있고 현재 위치보다 값이 작은 경우에만 이동하여 dfs 함수를 재귀적으로 호출한다. 이는 내리막길만 이동할 수 있다는 조건을 만족하기 위해서이다.
• 각 위치에서의 경로 수를 dp 배열에 저장하고 반환한다.

5. 입력 처리 및 함수 호출

m, n, *arr = map(int, sys.stdin.read().split())
it = iter(arr)
grid = [[next(it) for _ in range(n)] for _ in range(m)]
print(count_paths(m, n, grid))

• 표준 입력으로부터 그리드의 크기 m과 n, 그리고 그리드의 요소들을 입력받는다.
• arr 리스트를 이용해 그리드를 생성하고, count_paths 함수를 호출하여 경로 수를 계산한 후 출력한다.

이 알고리즘은 DFS를 사용하여 모든 경로를 탐색하고, 이미 계산된 경로 수는 dp 배열에 저장하여 중복 계산을 방지한다. 이를 통해 효율적으로 출발점에서 도착점까지의 경로 수를 계산할 수 있다.