[백준] 1753번 - 최단경로

최단경로

 

 

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1 

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1 

0
2
3
7
INF

 

문제 접근 방법

1. 왜 다익스트라 인가?

• 가중치(Weight)가 있음: 간선마다 비용(1~10)이 다르므로 BFS로는 최단 거리를 구할 수 없습니다.
• 음수 가중치가 없음: 가중치가 모두 자연수이므로 벨만-포드(Bellman-Ford) 같은 느린 알고리즘을 쓸 필요가 없습니다.
• 시간 복잡도 제한: 정점(V)이 2만 개, 간선(E)이 30만 개입니다.
  • 일반적인 2중 반복문 다익스트라(O(V2))를 쓰면 20,0002=4억 번 연산으로 시간 초과(1초)가 납니다.
  • 따라서 **우선순위 큐(Min-Heap)를 이용한 다익스트라(O(ElogV))**를 써야 합니다.

2. 핵심 자료구조: 우선순위 큐 (Min-Heap) 현재 갈 수 있는 노드 중 가장 비용이 적은 노드를 항상 먼저 꺼내서 방문해야 합니다. 이를 위해 최소 힙을 사용합니다.

import sys
import heapq

# 빠른 입력을 위해 sys.stdin.readline 사용
input = sys.stdin.readline
INF = int(1e9) # 무한대 값 설정

V, E = map(int, input().split()) # V: 정점 개수, E: 간선 개수
K = int(input()) # K: 시작 정점 번호


graph = [[] for _ in range(V + 1)] # 각 노드에 연결된 간선 정보를 담는 리스트
distance = [INF] * (V + 1) # 최단 거리 테이블을 모두 무한대로 초기화


# 모든 간선 정보 입력받기
for _ in range(E):
    u, v, w = map(int, input().split())     # u번 노드에서 v번 노드로 가는 비용이 w
    graph[u].append((v, w))

def dijkstra(start):
    q = []
    # 시작 노드로 가는 최단 경로는 0으로 설정하고, 큐에 삽입
    # (비용, 노드번호) 순서로 넣어야 비용 기준 정렬됨
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q) # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        
        if distance[now] < dist: # 큐에서 꺼낸 거리가 기존 최단 거리보다 크면
            continue
            
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1] # i[1]은 가중치
            
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]: # i[0]은 목적지 노드
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(K)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, V + 1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

코드  설명 

1. sys.stdin.readline: 데이터의 양이 많을 때(E 최대 30만), 파이썬의 기본 input()은 느려서 시간 초과가 날 수 있습니다. 꼭 sys 라이브러리를 써야 합니다.
2. heapq 사용법:
   • 파이썬의 heapq는 기본적으로 최소 힙입니다. 가장 작은 값이 먼저 나옵니다.
   • 튜플 (비용, 노드번호) 형태로 넣으면, 맨 앞의 비용을 기준으로 정렬됩니다.
3. if distance[now] < dist: continue:
   • 이 부분이 시간 복잡도를 줄이는 핵심입니다.
   • 큐에 같은 노드가 여러 번 들어갈 수 있는데(더 짧은 경로가 발견될 때마다), 이미 처리된(더 짧은 경로로 방문한) 노드를 큐에서 또 꺼냈을 때는 다시 계산하지 않고 넘어가야 합니다.
4. graph[u].append((v, w)):
   • 입력에서 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다고 했습니다.
   • 하지만 다익스트라 알고리즘 특성상, 인접 리스트에 다 넣어두면 알아서 가장 작은 가중치 경로가 먼저 선택되어 최단 거리가 갱신되므로 별도의 예외 처리는 필요 없습니다.