<aside> 🔥 이코테 39번 문제

</aside>

<aside> 🔥 문제 정리

첫째줄에 t : 테스트 케이스의 수가 주어진다.

둘째줄에 n : n x n의 2차원 그래프 크기가 주어진다.

셋째줄에 n개의 줄이 주어지고 탐사 공간의 크기가 주어진다.

[0][0] 칸에서부터 [n-1][n-1]로 이동하는 최소 비용을 출력하자.

입력값
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 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4

출력값
20
19
36

</aside>

<aside> 🔥 접근 방법

다익스트라를 활용해서 시작점에서 상하좌우를 탐색해 나간다.

탐색을 마치면 [n-1][n-1]은 최단거리로 계산될거 같다.

따라서 graph의 마지막을 출력하면 될거같다.

</aside>

<aside> 🔥 코드 진행

1. 입력값을 txt파일로 따로 저장해서 불러오는 방식으로 작성했다.

   바로 그래프를 만들어주고 다익스트라 함수를 호출해준다.

   with open('../test_case2.txt') as f:
       sys.stdin = f
       input = sys.stdin.readline
       t = int(input())
       for _ in range(t):
           n = int(input())
           graph = [list(map(int, input().split())) for _ in range(n)]
           INF = int(1e9)
   
           # 결과 출력
           print(dijkstra(graph, 0, 0)[-1][-1])
   

2. 다익스트라 함수에 그래프와 시작 좌표 (x, y)를 넘겨준다.

   거리 테이블 생성 및 heap을 사용해서 시간복잡도를 줄이도록 한다.

   def dijkstra(graph, x, y):
       # 상하좌우
       dx = [0, 0, -1, 1]
       dy = [-1, 1, 0, 0]
       N = len(graph)
   
       # 거리 테이블 생성
       dist = [[INF] * (N) for _ in range(N)]
   
       # heapq 사용
       # 튜플로 (탐사비용, x좌표, y좌표) 입력
       q = []
       heapq.heappush(q, (graph[0][0], x, y))
   
       # 첫 시작점 비용 입력
       dist[0][0] = graph[0][0]
   

3. heap에 값이 있는동안 반복하여 상하좌우를 탐색해나간다.

   # heap에 값이 있는동안 반복
       while q:
           # 누적비용, x, y 좌표 꺼내옴.
           acc, x, y = heapq.heappop(q)
   
           # 테이블에 거리가 누적거리보다 작으면 건너뛰기.
           if dist[x][y] < acc:
               continue
   
           # 상하좌우 탐색
           for i in range(4):
               nx = x + dx[i]
               ny = y + dy[i]
   
               # 상하좌우가 범위에 있을 경우
               if 0 <= nx < n and 0 <= ny < n :
                   # 새로운 누적값 계산
                   cost = acc + graph[nx][ny]
                   # 누적값이 테이블에 기록되어있는 것보다 적을경우
                   if cost < dist[nx][ny] :
                       # 업데이트
                       dist[nx][ny] = cost
                       heapq.heappush(q, (cost, nx, ny))
       return dist
   

</aside>