Algorithm - 알리바바와 40인의 도둑(동적 계획법)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[알리바바와 40인의 도둑(동적 계획법)]

 

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있다.

알리바바는 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다.

계곡의 돌다리는 N*N개의 돌로 구성되어 있으며, 각 돌다리들은 높이가 서로 다르다.

해당 돌다리를 건널 때 돌의 높이만큼 에너지가 소비되며, 반드시 최단거리로 이동한다.

즉, 현재지점에서 오른쪽 또는 아래쪽으로만 이동해야 한다.

 

3*3 계곡 돌다리

 

N*N의 계곡 돌다리 격자정보가 주어지면, (1, 1)에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하시오. 만약, 위의 예시처럼 N=3인 돌다리 격자정보가 주어진다면 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 14이다. (ex. 3+2+3+4+2 = 14)

 

 

*입력 설명

첫 번째 줄에는 자연수 N(1 ≤ N ≤ 20)이 주어진다.

두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이정보가 주어진다.

단, 돌다리의 높이는 10보다 작은 자연수이다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안(1) : Bottom-Up

import sys
sys.stdin = open('AA/input_79.txt', 'rt')

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dy = [[0]*n for _ in range(n)]
    dy[0][0] = arr[0][0]
    for i in range(1, n):
        dy[0][i] = dy[0][i-1] + arr[0][i]
        dy[i][0] = dy[i-1][0] + arr[i][0]
    for i in range(1, n):
        for j in range(1, n):
            dy[i][j] = min(dy[i-1][j], dy[i][j-1]) + arr[i][j]
    print(dy[n-1][n-1])
    
# 출력 : 25

 

답안(2) : Top-Down(재귀함수 & 메모이제이션)

import sys
sys.stdin = open('AA/input_79.txt', 'rt')

def DFS(x, y):
    if dy[x][y] > 0: # 컷엣지(메모이제이션)
        return dy[x][y]
    if x == 0 and y == 0:
        return arr[0][0]
    else:
        if y == 0:   # 0열에 위치하는 경우
            dy[x][y] = DFS(x-1, y) + arr[x][y]
        elif x == 0: # 0행에 위치하는 경우
            dy[x][y] = DFS(x, y-1) + arr[x][y]
        else:
            dy[x][y] = min(DFS(x-1, y), DFS(x, y-1)) + arr[x][y]
        return dy[x][y]
        
if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dy = [[0]*n for _ in range(n)]
    print(DFS(n-1, n-1))
    
# 출력 : 25

 

input_79.txt(입력)

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

 

 

중요내용(Bottom-Up)

1. 2차원 리스트 dy에는 해당 지점까지 도착하는데 소비되는 최소에너지값을 저장한다.
2. dy[i][j]는 출발지점(dy[0][0])을 포함해서 해당 지점까지 도착하는데 소비되는 최소에너지 크기를 의미한다.
3. 2차원 리스트 dy의 0행과 0열은 해당 지점에 도달하는 경로가 1가지 밖에 없으므로 2차원 리스트 dy에 초기값을 미리 설정해두는 것이다.
4. 만약, 특정 위치에 도달할 수 있는 경로가 2가지라면 해당 위치까지 도달하는데 소비되는 에너지가 최소인 값을 dy[i][j]에 저장한다.
5. 문제의 설명과 달리 위의 코드답안에서는 출발지점이 (0, 0)이고 최종 도착지점이 (N-1, N-1)이다.
6. 또한, 2차원 리스트 dy의 0행과 0열 위치는 이미 초기값을 가지고 있기 때문에 실질적인 시작지점은 dy[1][1]이 된다.

 

중요내용(Top-Down)

1. 탑다운 방식에서는 상태트리의 최상단 부모노드가 도착지점인 DFS(N-1, N-1)이다.
2. 참고로, x는 2차원 리스트의 행을 의미하고 y는 2차원 리스트이 열을 의미한다.
3. 2차원 리스트 dy의 0행과 0열 위치에서는 DFS() 재귀함수의 호출이 반드시 한 방향으로만 이루어져야 한다.
4. 즉, 상태트리에서 뻗어나가는 노드가 오직 1개만 존재해야 한다. (해당 위치에 도착하는 경로가 오직 1개이기 때문)
5. 동일한 지역을 재귀함수로 호출하는 경우에는 메모이제이션을 통해 더 이상 재귀함수를 호출하지 않고(상태트리에서 노드를 뻗지 않고) 2차원 리스트 dy에 이미 저장된 값을 리턴해줘야 한다.(컷엣지)
6. 참고로, 2차원 리스트 dy에는 해당 위치에 도달하는데 소비되는 에너지량을 저장하고 이를 메모이제이션(컷엣지)에 활용한다.
7. 만약, 메모이제이션을 하지 않는다면 N의 크기가 클수록 코드실행에 걸리는 시간이 기하급수적으로 늘어날 것이다. (시간복잡도 개선을 위해 메모이제이션 필수)