[ACM-ICPC] 화성탐사

 

입력 예시

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

 

출력예시

20
19
36

 

 

 

 

 

 

 

초기접근

---

처음에는 다이나믹 프로그래밍으로 접근했다.

 

2차원 공간의 왼쪽 위 -> 오른쪽 아래로 가장 빠르게 가는 경우에서

 

상하좌우로 이동하는 방향에서 좌, 상은 쓸모없는 움직임이라고 생각했다.

(한번에 가는것이 돌아가는 것보다 항상 비용이 적을 것이라는 오해)

 

그래서 우, 하 (오른쪽으로 가기, 아래로 가기) 의 움직임만 고려한 다이나믹 프로그래밍으로 풀었다.

 

그랬더니 입력 예시의 2번째 테스트 케이스의 답이 다르게 나왔다.

 

오른쪽으로가기, 아래로가기만을 고려한 최단경로

 

 

 

하지만 두번째 테스트 케이스의 경우 더 빠른 경로가 존재했다.

 

이 경로를 해결할 코드를 작성해야 했다.

 

 

 

 

 

해결 아이디어

---

1. 2차원 배열 상의 공간을 상하좌우가 다 연결되어있는 graph로 본다.
2. (0,0) 에서 출발해 (n-1, n-1) 로 가는 최단경로를 다익스트라 알고리즘으로 구한다.

 

 

 

해결코드

---

import heapq

t = int(input())

while t > 0:

    n = int(input())
    data = []
    for i in range(n):
        data.append(list(map(int, input().split())))

    dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    INF = int(1e9)
    distance = [[INF]*n for i in range(n)]

    q = []
    q.append((data[0][0], 0, 0))
    distance[0][0] = data[0][0]

    while q:
        dist, x, y = heapq.heappop(q)

        if distance[x][y] < dist:
            continue

        for d in dir:
            nx = d[0] + x
            ny = d[1] + y

            if 0 <= nx < n and 0 <= ny < n:
                cost = dist + data[nx][ny]

                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(q, (cost, nx, ny))

    print(distance[n-1][n-1])

    t -= 1