[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 7

알리바바와 40인의 도둑(Bottom-Up)

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.
알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다.
계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.
해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다.즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다.
N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요.만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면

(1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다.

▣ 입력설명
첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다.
두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

▣ 출력설명
첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.

▣ 입력예제 1

5
3 7 2 1 9
5 8 3 9 2
5 3 1 2 3
5 4 3 2 1
1 7 5 2 4

▣ 출력예제 1
25

바텀업

import sys
sys.stdin = open("input.text", "rt")
from collections import deque

#최단거리 + 그래프 
#BFS
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = g[0][0]

for i in range(1,n):
    dp[0][i] = dp[0][i-1] + g[0][i]
    dp[i][0] = dp[i-1][0] + g[i][0]

for i in range(1,n):
    for j in range(1,n):
        dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + g[i][j]

print(dp[n-1][n-1])

탑다운

import sys
sys.stdin = open("input.text", "rt")
from collections import deque

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = g[0][0]

def DFS(x,y):
    if dp[x][y] > 0:
        return dp[x][y]
    if x == 0 and y == 0: #출발 지점
        return g[0][0]
    else:
        if y == 0:
            dp[x][y] =  DFS(x-1, y) + g[x][y]
        elif x == 0:
            dp[x][y] = DFS(x, y-1) + g[x][y]
        else:
            dp[x][y] = min(DFS(x-1, y), DFS(x,y-1)) + g[x][y]
        return dp[x][y]

DFS(n-1,n-1)
print(dp[n-1][n-1])

코멘트

해당 문제는 BFS로도 가능하지만 dp로 생각해보겠다. 먼저 문제에서 오른쪽 혹은 아래쪽으로만 가능하다고 명시했다. 그렇기에 올 수 있는 경우의 수가 몇개 없기 때문에 이전까지의 최단거리 + 현재 값을 더해주는 방식으로 계산할 수 있다.

• 그리고 0행은 왼쪽에서 오는 경우밖에 없다
• 0열 역시 위에서 내려오는 경우밖에 없다.
  • 그렇기에 dp 테이블의 0행, 0열을 고정할 수 있다.