[이코테] CH09 최단경로 실전문제 39번 화성 탐사

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findMin():
    dx = [-1,0,1,0]
    dy = [0,1,0,-1] # 상하좌우 움직일 수 있으므로!! 
    q = []
    heapq.heappush(q,(graph[0][0],0,0)) # 비용, row, col (start)
    while q:
        dist,row,col  = heapq.heappop(q) # 힙에서 우선순위대로 원소를 추출한다
        if distance[row][col] < dist:  # 이미 갱신이 끝난 원소이므로 코드를 점프
            continue
        for i in range(4): # 원래 문제에서는 graph[i] 에 대해서 해줬지만 상황이 다르므로 상하좌우에 대해서 실행
            nx = row + dx[i]
            ny = col + dy[i]
            if nx < 0 or ny < 0 or nx >=N or ny>=N:
                continue
            cost = dist + graph[nx][ny] # 총 비용은 추출한 dist와 다음 원소의 비용의 합 
            if cost < distance[nx][ny]: # 만약 이 총 비용이 더 작다면?
                distance[nx][ny] = cost # 총 비용을 더 작은 값으로 갱신해주고
                heapq.heappush(q,(distance[nx][ny],nx,ny)) # 다음 실행해줄 원소로 heappush를 해준다.
    return distance[N-1][N-1] 
        


T = int(input())
minarr = []
for _ in range(T):
    N = int(input()) 
    graph = []
    distance = [[INF] * (N+1) for _ in range(N+1)] # 여기서 distance 배열은 최단거리 테이블을 만들어주는 행위, 현재 노드까지 얼마나 최소의 비용으로 올 수 있는지
    for i in range(N):
        graph.append(list(map(int,sys.stdin.readline().split()))) # 그냥 일차원 배열 선언해주고 List 자체를 append 해주는 방식으로 해주면 된다 !! 
        minarr.append(findMin())

for i in minarr:
    print(i)
    print()

솔직히 후반에 꼬여서 답안지 조금 참고했습니다 .

distance 배열이 2차로 나오니까 

코드 끝부분이 조금 헷갈리더라고요

 

일단 이 문제는 다익스트라로 해결했고 그 이유는 

시작점 [0][0] 명시 

N이 125 이하라고 명시해서 플로이드 워셜인가 했지만 이차원배열이므로 시간복잡도가 매우 오래 걸릴 것이라고 판단했습니다.

 

코드는 헷갈렸으므로 창 닫고 다시한번 짜봐야겠습니다

 

헷갈렸던 점

1. distance[nx][ny]와 graph[nx][ny] 

distance[nx][ny]는 현재 인덱스까지 오는데 필요한 최소비용

graph[nx][ny]는 현재 인덱스에서의 비용이다 !! 헷갈리지 말 것