[BOJ] 1753 - 최단경로 (Java)

알고리즘

• 그래프 이론
• 데이크스트라
• 최단 경로

1. 문제

2. Idea

• 가중치가 존재하는 방향 그래프
• 다익스트라 사용 : 단일 출발지 최단 경로 문제를 해결하는데 적합
• 우선순위 큐 사용
• 플로이드-워셜 알고리즘 사용 시 모든 정점의 모든 쌍 최단거리를 계산하게 되므로 메모리 초과가 난다.

3. 풀이

3.1. 노드 클래스 정의

• Node 클래스는 그래프, 각 노드를 표현
• Comparable 인터페이스를 구현하여 우선순위 큐에서 최단거리 기준으로 정렬

    static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

3.2. 그래프 입력 및 초기화

• int N: 정점 수
• int M: 간선 수
• int start: 시작 정점
• 인접 리스트 graph를 사용하여 그래프를 표현
• dist 배열을 사용하여 시작점으로부터 각 노드까지의 최단 거리를 저장
• 초기값: 무한대(INF)

        int INF = 1000000000;
        int N = Integer.parseInt(st.nextToken()); // 정점 수
        int M = Integer.parseInt(st.nextToken()); //간선 수
        int start = Integer.parseInt(br.readLine()); // 시작 정점

        List<List<Node>> graph = new ArrayList<>(); //인접 리스트 생성
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>()); //각 정점에 대한 거리를 저장할 배열 생성
        }

        // 입력 저장
        for (int i = 0; i < M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st2.nextToken());
            int e = Integer.parseInt(st2.nextToken());
            int w = Integer.parseInt(st2.nextToken());
            graph.get(s).add(new Node(e, w)); // s->e 가중치: w
            // 해당 시작 정점에 대한 도착점,가중치에 대한 배열에 모두 저장
        }

        int[] dist = new int[N + 1]; // 시작점으로부터 각 노드까지의 최단 거리를 저장할 배열
        Arrays.fill(dist, INF); //모든 거리에 대한 초기값은 INF
        dist[start] = 0; // 시작점에 대한 거리는 0

3.3. 다익스트라 알고리즘 수행

• 시작 노드를 우선순위 큐에 추가하고, 큐에서 최소 거리를 갖는 노드를 반복적으로 꺼내어 최단 거리를 업데이트

        PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선 순위 큐(최소 힙) 생성
        //노드 객체를 가중치 기준으로 정렬
        pq.add(new Node(start, 0)); // 시작 노드를 큐에 추가. 이때 시작 노드의 가중치=0

        while (!pq.isEmpty()) {
            Node current = pq.poll(); // 가장 작은 가중치를 가진 노드 poll
            int currentVertex = current.vertex; //현재 노드의 인덱스
            int currentWeight = current.weight; //현재 노드까지의 최소 가중치(최단 거리)

            if (currentWeight > dist[currentVertex]) {
            // 만약 현재 노드까지의 거리가 이미 기록된 거리보다 크다면, 이미 더 짧은 경로가 있다는 의미이므로 이 노드는 무시하고 continue
                continue;
            }

			// 현재 노드(currentVertex)의 모든 인접 노드(neighbor)를 탐색
            for (Node neighbor : graph.get(currentVertex)) {
                int nextVertex = neighbor.vertex; // 인접 노드의 인덱스
                int weight = neighbor.weight; //현재노드->인접 노드로의 가중치
                int newDist = dist[currentVertex] + weight; // 시작 노드에서 인접 노드까지의 새로운 잠재적 최단 거리

                if (newDist < dist[nextVertex]) { // 새로운 거리 < 기록된 거리
                    dist[nextVertex] = newDist; // 기록의 최단거리 업데이트
                    pq.add(new Node(nextVertex, newDist)); // 인접 노드를 우선순위 큐에 추가하여, 이 노드도 탐색 대상으로 포함
                }
            }
        }

3.4. 결과 출력

• 시작점에서 각 노드로의 최단 거리를 출력
• 경로가 없는 경우 INF 출력

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            if (dist[i] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }

4. 전체코드

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

public class Week13 {

    static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

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

        int INF = 1000000000;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine());

        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // 입력 저장
        for (int i = 0; i < M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st2.nextToken());
            int e = Integer.parseInt(st2.nextToken());
            int w = Integer.parseInt(st2.nextToken());
            graph.get(s).add(new Node(e, w));
        }

        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentVertex = current.vertex;
            int currentWeight = current.weight;

            if (currentWeight > dist[currentVertex]) {
                continue;
            }

            for (Node neighbor : graph.get(currentVertex)) {
                int nextVertex = neighbor.vertex;
                int weight = neighbor.weight;
                int newDist = dist[currentVertex] + weight;

                if (newDist < dist[nextVertex]) {
                    dist[nextVertex] = newDist;
                    pq.add(new Node(nextVertex, newDist));
                }
            }
        }

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            if (dist[i] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }
    }
}