[알고리즘] 알리바바와 40인의 도둑(Top-Down)
(문제) 알리바바와 40인의 도둑(Top-Down)
알리바바는 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)도착지로 가기 위한 최소 에너지를 출력한다.
테스트케이스
입력예제 | 출력예제 |
---|---|
3 3 3 5 2 3 4 6 5 2 |
14 |
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 |
25 |
10 9 4 6 7 5 1 3 1 5 3 2 4 6 3 9 8 9 1 3 2 6 9 6 2 4 1 8 3 7 8 3 9 7 5 3 1 3 6 6 1 3 6 6 3 8 9 6 7 7 4 1 4 5 3 1 8 1 9 1 3 7 3 1 1 7 7 3 7 4 3 8 5 6 7 7 9 1 8 3 2 2 8 7 4 3 4 2 9 2 9 1 1 1 2 6 1 3 8 1 9 |
69 |
해결방법
이런 상태 Tree 형태가 그려진다.
이에 맞게 코드를 생각한다.
다이나믹 프로그래밍으로 저장할 dt 리스트를 생성하여, 각 node와 비교하여 최소 값을 찾으면 그 값과 현재 좌표 자체에 있는 값을 더해서 dt리스트에 저장한다.
만약 왼쪽 좌표가 없을 경우 y축을 이용하여 최소 값을 알아낸다.
만약 위쪽 좌표가 없을 경우 x축을 이용하여 최소 값을 알아낸다.
Top-down 방식으로 마지막으로 재귀해서 다시 돌아와서 해당 dt 좌표의 값을 구하면 된다.
동작 시각화
테스트케이스
입력
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
결과
25
dt 테이블 형태
코드
def DFS(y, x):
if dt[y][x]:
return dt[y][x]
if x == 0 and y == 0:
return rocks[0][0]
else:
# 행이 가장 위에 있을 경우 위쪽을 볼 수 없기에 왼쪽만 조회해서 더함
if y == 0:
dt[y][x] = DFS(y, x-1) + rocks[y][x]
# 열이 가장 왼쪽에 있을 경우 왼쪽을 볼 수 없기에 위쪽만 조회해서 더함
elif x == 0:
dt[y][x] = DFS(y-1, x) + rocks[y][x]
# 왼쪽 혹은 위쪽 중에서 값이 최소인 것을 골라서 더함
else:
dt[y][x] = min(DFS(y, x-1), DFS(y-1, x)) + rocks[y][x]
return dt[y][x]
n =int(input())
rocks = [list(map(int, input().split())) for _ in range(n)]
dt = [[0] * n for _ in range(n)]
DFS(n-1, n-1)
print(dt[n-1][n-1])
댓글남기기