코드

import heapq
import sys

# 무한
INF = int(1e9)

# 노드의 개수, 간선으 ㅣ개수
n, m = map(int, input().split())

# 시작 노드
start_node = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for _ in range(n+1)]

# 최단 거리 테이블 (무한으로 초기화)
distance = [INF] * (n+1)

# 모든 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    
    # a 노드에서 b노드로 가는 비용 : c
    graph[a].append((b, c))
    
# 다익스트라 구현
def dijkstra(start_node):
    
    # 최소힙으로 구현할 것이므로 큐 생성
    q = []
    
    # 시작 노드부터 알고리즘이 시작
    # 시작 노드에서 시작노드로 가는 비용은 0
    # 튜플로값을 넣을 때, (가치, 물건)의 개념으로 입력 => 가치를 기준으로 가치가 우선순위
    # 가치가 낮을 수록 먼저 삭제
    # 내부적으로 정렬이 돼있지 않으므로 무조건 가치가 낮은 애가 먼저 삭제됨
    heapq.heappush(q, (0, start_node))
    
    # 시작 노드의 최단 거리 테이블을 0으로 변경
    distance[start_node] = 0
    
    # q가 빌 떄 까지
    while q:
        # 거리, 현재 있는 노드
        dist, now = heapq.heappop(q)
        
        # 현재 노드의 최단 거리 테이블이 dist보다 작다
        # 그 뜻은 최단 거리 테이블에 있는 값이 가장 작은 값이다
        # 즉 최단 경로에 부합하므로
        # 연산을 하지 않고 무시한다
        # 초기값이 INF으로 설정한 이유도 이 조건에 걸리게 하기 위함
        if distance[now] < dist:
            continue
            
        # 현재 노드와 연결된 다른 인접한 노드들 확인
        for i in graph[now]:
            # 노드까지 이동하는 비용 계산
            # dist는 now까지 오는데 쓴 비용
            # i[1]은 now에서 i번째 노드까지 가는데 쓰는 비용 (c)
            cost = dist + i[1]
            
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            # 즉 cost가 distance[i[0]]보다 더 짧은 경우
            # i[0] : 다음 노드
            # 즉 distance[다음 노드]가 되고 distance[다음 노드]의 의미는 다음 노드가 갖는 최단 거리 테이블 값이다
            if cost < distance[i[0]]:
                # 더 작으니까 최단 거리 테이블을 업데이트
                distance[i[0]] = cost
                
                # cost : 비용
                # i[0] : 노드 (start에서 이동한 다음 노드가 됨)
                heapq.heappush(q, (cost, i[0]))
                
# 다익스트라 수행
dijkstra(start_node)

# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
    
    # 도달할 수 없으면 INF 그대로 출력
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

문제 해설

다익스트라 알고리즘 문제이다.

최소힙을 이용하여 시간적인 성능을 개선시킨 방식으로 문제를 해결하였다.

매우 기본에 충실한 문제이므로 몇번이고 분석하고 자주 복습하여 문제를 풀어보고 다른 최단 경로 문제 역시 수월하게 풀 수 있을 만큼 연습해야겠다.

댓글남기기

참고