1753번: 최단경로

문제

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

• 입력: 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 둘째 줄에는 시작 정점의 번호 K가 주어집니다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 주어집니다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 의미입니다.
• 출력: 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 시작점 K에서 i번 정점으로 가는 최단 경로의 경로값을 출력합니다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력합니다.

링크: https://www.acmicpc.net/problem/1753

풀이: 우선순위 큐를 활용한 다익스트라(Dijkstra) 알고리즘

가중치가 양수인 그래프에서 단일 출발점 최단 경로를 구하는 문제이므로 데이크스트라(Dijkstra) 알고리즘을 사용하는 것이 가장 정석입니다. 정점과 간선의 개수가 많으므로, 시간 복잡도를 O(E log V)로 최적화하기 위해 우선순위 큐(Priority Queue)를 활용합니다.

• 그래프 표현 (인접 리스트): 간선의 개수(E)가 정점의 개수(V)의 제곱보다 훨씬 작을 수 있는 희소 그래프이므로, 2차원 배열 대신 List<Node>[] 형태의 인접 리스트를 사용하여 메모리를 절약하고 탐색 속도를 높입니다.
• 우선순위 큐 (Min-Heap): 최단 거리가 가장 짧은 노드를 먼저 탐색하기 위해 우선순위 큐를 사용합니다. 람다식 (n1, n2) -> Integer.compare(n1.w, n2.w)를 통해 누적 거리(w)를 기준으로 오름차순 정렬되도록 구성했습니다.
• 거리 갱신 (Relaxation):
  • 시작점 K의 거리를 0으로 초기화하고 큐에 넣습니다.
  • 큐에서 꺼낸 노드(cur)의 기록된 누적 거리(cur.w)가 현재 거리 배열에 기록된 값(d[cur.v])보다 크다면, 이미 처리된(더 짧은 경로를 찾은) 노드이므로 건너뜁니다(continue).
  • 현재 노드와 인접한 다음 노드(next)들을 순회하며, (현재까지의 최단 거리 + 다음 노드로 가는 가중치)가 기존에 기록된 다음 노드의 최단 거리(d[next.v])보다 작을 경우에만 거리를 갱신하고 큐에 추가합니다.
• 결과 출력: 모든 탐색이 끝난 후 거리 배열 d를 순회하며, 값이 초기값(Integer.MAX_VALUE) 그대로라면 도달할 수 없는 곳이므로 "INF"를, 아니라면 최단 거리를 출력합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    // 그래프의 정점과 누적 거리 정보를 담을 클래스
    static class Node {
       int v, w;

       public Node(int v, int w) {
          this.v = v;
          this.w = w;
       }
    }

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int v = Integer.parseInt(st.nextToken());
       int e = Integer.parseInt(st.nextToken());
       int k = Integer.parseInt(br.readLine());

       // 인접 리스트 초기화
       List<Node>[] adj = new ArrayList[v + 1];
       for (int i = 0; i <= v; i++) {
          adj[i] = new ArrayList<>();
       }

       // 간선 정보 입력 (방향 그래프)
       for (int i = 0; i < e; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());

          adj[a].add(new Node(b, w));
       }

       // 최단 거리 배열 초기화
       int[] d = new int[v + 1];
       Arrays.fill(d, Integer.MAX_VALUE);

       // 누적 거리 기준 오름차순 정렬되는 우선순위 큐
       PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.w, n2.w));
       
       // 시작점 설정
       pq.add(new Node(k, 0));
       d[k] = 0;
       
       // 다익스트라 탐색 진행
       while (!pq.isEmpty()) {
          Node cur = pq.poll();

          // 이미 갱신된 더 짧은 경로가 있다면 패스 (시간 최적화)
          if (d[cur.v] < cur.w) {
             continue;
          }

          // 인접 노드 탐색 및 거리 갱신
          for (Node next : adj[cur.v]) {
             if (d[next.v] > cur.w + next.w) {
                d[next.v] = cur.w + next.w;
                pq.add(new Node(next.v, d[next.v]));
             }
          }
       }

       // 결과 출력
       for (int i = 1; i <= v; i++) {
          bw.write((d[i] != Integer.MAX_VALUE ? d[i] + "\n" : "INF\n"));
       }

       bw.flush();
    }
}

알고리즘 분류

그래프 이론 (Graph Theory), 최단 경로 (Shortest Path), 데이크스트라 (Dijkstra)