알리바바와 40인의 도둑 - python

<문제>

알리바바는 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

 

<설명>

이문제 같은경우 Bottom-up 방식 Top-down 방식 2가지 방식이 존재한다.

1) Bottom-up 방식 같은 경우에는 이차워 리스트 DP테이블을 만든 후에 해당 값에 저장을 한다. 맨처음 입력값중 L[x][y] 라할때 x가 0이거나 y가 0인 값들(행이 0이거나 열이 0일때) 먼저 반복문을 돌린다. 행이 0이거나 열이 0일때는 오른쪽 또는 아래로 밖에 갈 수 없기에 행이 0일때는 왼쪽값과 자기자신값을 더한값을 저장하고 열이 0일때는 위에값과 자기자신의 값들을 더해서 저장한다

이런식으로 만든다음에 이제 나머지 빈칸을 채워주면된다 나머지 빈칸 같은 경우에는 왼쪽 또는 위쪽값중에서 작은값과 해당 자리에 입력한 자기자신의 값을 더한 값을 저장한다. 이런식으로 값들을 채워주면 마지막 위치에 저장된 값을 출력해주면된다.

 

2) Top-down 같은 경우에는 재귀함수를 사용한다. 이때 메모제이션을 활용해서 가지치기를 진행한다. 

위 트리로 설명하자면, 맨 마지막에서 왼쪽 또는 위로 간다. 갈때 마다 해당 지점의 값들을 더해가면서 가고 가장 작은 값들을 선택해서 더해간다. 그러다 행이 0이면 왼쪽으로만 열이 0일경우 위쪽으로만 간다. 이때 메모제이션 같은 경우 그림에서 D(1,1)이 2번나오는데 값들을 DP테이블에 저장해놨다가 다른 탐색때 같은 위치가 나오면 계산을하지말고 DP테이블에 저장된 값을 가져오면 된다.

 

<코드>

#Bottom-Up 방식
n = int(input())
L = [list(map(int,input().split())) for _ in range(n)]
DP = [[0]*n for _ in range(n)]
DP[0][0] = L[0][0]
for i in range(1,n):
    DP[0][i] = DP[0][i-1] + L[0][i]
for i in range(1,n):
    DP[i][0] = DP[i-1][0] + L[i][0]

for i in range(1,n):
    for j in range(1,n):
        if DP[i-1][j] <= DP[i][j-1]:
            DP[i][j] = DP[i-1][j] + L[i][j]
        else:
            DP[i][j] = DP[i][j-1] + L[i][j]
print(DP[n-1][n-1])

#Top-Down 방식
def DFS(x,y):
    if DP[x][y] > 0:
        return DP[x][y]
    if x == 0 and y == 0:
        return L[x][y]
    else:
        if y == 0:
            DP[x][y] = DFS(x-1,y) + L[x][y]
        elif x == 0:
            DP[x][y] = DFS(x,y-1) + L[x][y]
        else:
            DP[x][y] = min(DFS(x-1,y), DFS(x,y-1)) + L[x][y]
        return DP[x][y]
    
    

n = int(input())
L=[list(map(int,input().split())) for _ in range(n)]
DP=[[0] * n for _ in range(n)]
print(DFS(n-1,n-1))