[Java] 백준 1753 최단경로

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

문제

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

풀이

시작점으로부터 다른 모든 정점으로의 최단경로를 구하는 문제

최단경로 -> BFS 고려
근데 이제 방향그래프와 가중치를 곁들인...

-> 다익스트라 알고리즘을 떠올려야 한다

최단경로 문제 푸는 방법
가중치 개념이 없는 단순 최소 경로 문제 → BFS
가중치 개념이 있고, 한 노드 기준으로 다른 노드까지의 최소 경로를 구하는 문제 → 다익스트라 ✅
가중치 개념이 있고, 모든 노드 기준으로 다른 노드까지의 최소 경로를 구하는 문제 → 플로이드 와샬

다익스트라 알고리즘

• 시작점과 도착할 지점의 정보가 주어진다.
• 연결된 노드 및 가중치 정보가 주어진다.
• 시작점과 모든 지점과의 거리 정보 리스트를 만든다.
• 현재 노드(시작점 포함)와 인접한 모든 노드와의 거리 중 최소 거리인 노드이면서 방문하지 않은 노드 순서대로 방문한다.
• 현재 노드까지의 최소거리 + 두 지점간 최소 거리 < 다음 지점까지 가는 거리 면 갱신
• 도착지점에 도착하면 알고리즘을 종료한다.

• (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 와 같이 정점, 간선의 개수가 매우 크기 때문에 인접행렬 대신 인접리스트에 간선 정보 저장

  인접 행렬 🆚 인접 리스트
  - 인접 행렬: $O(V^2)$
  - 인접 리스트: $O(V+E)$

1. 정점 간의 인접 리스트(+ 연결된 정점 & 가중치), 각 정점까지의 거리를 담은 배열(다른 정점까지의 거리를 모르므로 무한대로 가정) 생성

2. PriorityQueue에 시작 정점 추가(큐가 아닌 우선순위 큐를 쓰는 이유: 가중치가 적은 정점을 우선적 탐색)

3. 다음 정점 방문시, 현재 정점을 거쳐서 가는 경우가 최단경로라면 최댓값 배열 갱신, 이 경우에만 큐에 추가 -> 다익스트라 알고리즘

자바에서 우선순위 큐 구현

• 사용자 정의 객체를 PriorityQueue에 사용하려면 Comparable 인터페이스를 구현해야 함

class CustomObject implements Comparable<CustomObject> {
    private int priority;
    public CustomObject(int priority) {
        this.priority = priority;
    }
    @Override
    public int compareTo(CustomObject other) {
        return this.priority - other.priority;
    }
}
PriorityQueue<CustomObject> customQueue = new PriorityQueue<>();

• PriorityQueue는 내부적으로 힙 구조를 사용하여 O(log n) 시간 복잡도로 요소를 추가하고 제거함

정답코드

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

public class Main {
    public static class Node implements Comparable<Node> {
        int e;
        int v;

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

        @Override
        public int compareTo(Node n) {
            return this.v - n.v; // 가중치 크기 비교
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine()); // 시작정점

        // 간선 정보 -> 인접리스트 저장
        ArrayList<Node>[] adjList = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++) {
            adjList[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());

            // 시작, 도착, 가중치
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int wei = Integer.parseInt(st.nextToken());

            adjList[from].add(new Node(to, wei));
        }

        // 최단거리 갱신 테이블
        int[] table = new int[v + 1];

        Arrays.fill(table, Integer.MAX_VALUE); // 무한대로 초기화

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0)); // 시작정점: 0
        table[start] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            for (Node nxt : adjList[cur.e]) { // 다음 정점 탐색
                if (table[nxt.e] > table[cur.e] + nxt.v) { // 다음 노드까지의 최단 거리 > 현재까지 최단거리 + 다음 노드까지의 거리
                    table[nxt.e] = table[cur.e] + nxt.v; // 새로운 경로가 더 짧다면 업데이트
                    pq.add(new Node(nxt.e, table[nxt.e]));
                }
            }
        }
        for (int i = 1; i <= v; i++) {
            if (table[i] == Integer.MAX_VALUE) System.out.println("INF"); // 경로 없을때
            else
                System.out.println(table[i]);
        }
    }
}

• 참고한 블로그
  https://sookr5416.tistory.com/194