079 - 알리바바와 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 time
#import sys
#name = 'in5.txt'
#sys.stdin = open(name, 'rt')


def DFS(x, y, sum):
    global res
    if x == n-1 and y == n-1:
        # print(f'sum:{sum}')
        if res > sum:
            res = sum
        return
    else:
        for i in range(2):
            x1 = x+dx[i]
            y1 = y+dy[i]
            # print(x, y, dx[i], dy[i], i, x1, y1)
            if (x1 < n) and (y1 < n) and ch[x1][y1] == 0:
                ch[x1][y1] = 1
                sum = sum+a[x1][y1]
                # print(f'[{x},{y}]->[{x1},{y1}], sum:{sum}, {a[x][y]}/{a[x1][y1]}')
                DFS(x1, y1, sum)
                ch[x1][y1] = 0
                sum = sum-a[x1][y1]
        # if (sum > 30):
        #     return


if __name__ == '__main__':
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    ch = [[0]*n for _ in range(n)]
    res = float('inf')
    dx = [1, 0]
    dy = [0, 1]
    print(f'file name: {name}, table size: {n}')

    start = time.time()
    DFS(0, 0, a[0][0])
    end = time.time()
    p = end-start
    print(f'result:{res}, time={p:5.5}')
    print()

# =============== Dynamic, Bottom-UP ===============
    start = time.time()
    dy = [[0]*n for _ in range(n)]
    dy[0][0] = a[0][0]

    for i in range(1, n):
        dy[0][i] = dy[0][i-1]+a[0][i]
    for i in range(1, n):
        dy[i][0] = dy[i-1][0]+a[i][0]
    for i in range(1, n):
        for j in range(1, n):
            low = min(dy[i-1][j], dy[i][j-1])
            dy[i][j] = low+a[i][j]
    # for x in dy:
    #     print(x)

    end = time.time()
    print(f'result:{dy[-1][-1]}, time={end-start:5.5}')

# =============== Dynamic, Bottom-UP ===============

 

 

 

 

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


테스트 케이스를 15개만 사용해도 DFS와 다이나믹방식의 동작 시간 차이를 
명확히 알 수 있다.


file name: in3.txt, table size: 15
(DFS인 경우) result:100, time=91.085

(다이나믹 경우) result:100, time=0.00010872