[백준 BOJ] 1520 내리막길 (Python)

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

다이나믹 프로그래밍 문제이다.

 

배열을 순차적으로 순회하는 게 아니라 사방으로 움직이며 연산이 진행되기 때문에, DFS/BFS + DP의 조합으로 문제를 풀어야 한다.

 

1. DFS: 현재 지점에서 접근할 수 있는 곳의 모두 경우의 수를 더해가며, 출발점으로 되돌아온다. dp를 0으로 초기화하면, 경우의 수가 0일 때와 혼동되므로 -1로 초기화한다.

현재 지점을 이미 방문했다면 더 DFS를 들어갈 필요 없이 현재 저장된 DP값을 반환해주면 된다.

import sys
sys.setrecursionlimit(10 ** 8)
read = lambda: sys.stdin.readline().strip()

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


def dfs(cx, cy):
    if dp[cx][cy] != -1:						# 이미 방문한 곳이면 그만큼 더해줌
        return dp[cx][cy]

    cnt = 0
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]

        if not 0 <= nx < n or not 0 <= ny < m:
            continue
        if arr[nx][ny] >= arr[cx][cy]:
            continue
        cnt += dfs(nx, ny)

    dp[cx][cy] = cnt

    return dp[cx][cy]


n, m = map(int, read().split())
arr = [list(map(int, read().split())) for _ in range(n)]

dp = [[-1] * m for _ in range(n)]
dp[n - 1][m - 1] = 1
print(dfs(0, 0))

 

2. BFS: 큐 안에서 가장 높은 지점부터 방문하며, 접근 가능한 경로이면 경로의 개수를 더해주며 도착점까지 진행한다. 시작점의 DP 값을 1로 설정하고 시작하기 때문에, 0으로 초기화해도 된다.

높은 지점부터 방문해야 모든 경우의 수를 살필 수 있다. 

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

위의 경우, 32에서 30, 20으로 진행이 가능하여 큐에 삽입된다. 이어서 30에서 25로 이동이 가능하고, 25는 20으로 이동이 가능하다. 따라서 20은 30에서 오는 경로와 25에서 오는 경로 두 가지가 모두 계산돼야 한다. 이때, 높이를 고려하지 않으면 25보다 20이 먼저 큐에서 빠져나올 수 있다. 그러면 DP값이 올바르게(=2) 갱신되기 전에, 17로 잘못된 값(=1)을 전달하게 된다. 

import sys
read = lambda: sys.stdin.readline().strip()
from heapq import heappush, heappop

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


def bfs(x, y):
    q = [(-arr[x][y], x, y)]                # 우선순위큐 사용, 높은 곳 부터 방문하도록
    dp = [[0] * m for _ in range(n)]        # 그래야 중복방문 할 때 올바르게 갱신됨
    dp[x][y] = 1

    while q:
        cnt, cx, cy = heappop(q)

        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]

            if not 0 <= nx < n or not 0 <= ny < m:
                continue
            if arr[nx][ny] >= arr[cx][cy]:
                continue

            if dp[nx][ny] == 0:
                heappush(q, (-arr[nx][ny], nx, ny))
            dp[nx][ny] += dp[cx][cy]

    return dp


n, m = map(int, read().split())
arr = [list(map(int, read().split())) for _ in range(n)]

print(bfs(0, 0)[n - 1][m - 1])

파이썬은 최소힙이므로 음수로 바꾸어주었다.