080 - 알리바바와 40인의 도둑(Top-Down)

이번에는 079 문제를 다이나믹 방식인 Top-Down 과 Bottom-Up 을 비교하고 속도 차이를 알아보겠습니다.

 

import time
import sys
name = 'in5.txt'
sys.stdin = open(name, 'rt')


def DFS(x, y):

    if dy[x][y] > 0:
        return dy[x][y]
    if x == 0 and y == 0:
        return a[0][0]
    else:
        if x == 0:
            dy[x][y] = DFS(x, y-1)+a[x][y]
        elif y == 0:
            dy[x][y] = DFS(x-1, y)+a[x][y]
        else:
            dy[x][y] = min(DFS(x, y-1), DFS(x-1, y))+a[x][y]
        # print(x, y, dy[x][y])
        return dy[x][y]


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

# =============== Dynamic, Bottom-UP ===============
    print()
    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]
        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]

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

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


# =============== Dynamic, Top-Down ===============

    print()
    print('=============== Dynamic, Top-Down ===============')
    dy = [[0]*n for _ in range(n)]
    start = time.time()
    res = DFS(n-1, n-1)
    end = time.time()
    print(f'result:{res}, time={end-start:5.5}')
    print()

# =============== Dynamic, Top-Down ===============

 

 

테이블 사이즈는 20*20 입니다. Top-Down 방식은 재귀방식이므로 시간 단축을 위해서 메모이제이션 방식을 같이 사용했습니다.

 

실행 결과 - 일반적으로 Bottom-Up 방식이 빠른것을 확인했습니다.

 

 

file name: in5.txt, table size: 20

=============== Dynamic, Bottom-UP ===============
result:127, time=0.00018716

=============== Dynamic, Top-Down ===============
result:127, time=0.0002718