[SWEA/Python] 5251. 최소 이동 거리

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 다익스트라(dijkstra) 알고리즘을 활용한 풀이 (프림 알고리즘과 비슷)
2. 방문하지 않은 지점 중에서 이동거리가 최소인 지점을 찾는다.
3. 2의 지점과 인접한 지점 중에서 아직 방문하지 않은 지점에서 이동거리를 비교해서 갱신한다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def dijkstra(start):
    distance[start] = 0

    # 노드의 개수만큼 반복
    for _ in range(N+1):
        min_idx = -1
        min_value = float('inf')

        for i in range(N+1):
            if not visited[i] and distance[i] < min_value:
                min_idx = i
                min_value = distance[i]
        
        visited[min_idx] = 1

        for i in range(N+1):
            if mat[min_idx][i] and not visited[i]:
                distance[i] = min(distance[i], distance[min_idx]+mat[min_idx][i])


T = int(input())

for t in range(1, T+1):
    N, E = map(int, input().split())
    edges = [list(map(int, input().split())) for _ in range(E)]

    # 인접 행렬
    mat = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for s, e, w in edges:
        mat[s][e] = w
    
    visited = [0 for _ in range(N+1)]
    distance = [float('inf') for _ in range(N+1)]

    dijkstra(0)

    print('#{} {}'.format(t, distance[N]))