[백준] 1753번 : 최단경로 (JAVA)

인간몽쉘김통통·2024년 1월 6일

데이크스트라 백준 알고리즘 최단 경로

백준

목록 보기

42/92

문제

이해

방향 그래프 상에서 입력된 시작점에서 다른 정점까지의 최단거리를 구한다.

단, 그래프 상에서 서로 다른 정점 사이에는 여러 개의 간선이 존재할 수 있다.

경로가 존재하지 않는 경우에는 INF를 출력한다.

접근

방향그래프의 최단 경로를 구하는 문제이다. 문제처럼 거리의 가중치가 있는 최단 경로 문제는 보통 데이크스트라 알고리즘을 활용한다.

이전에 데이크스트라 문제를 다룬적 있지만 예전에 푼 문제라서 기억나지 않았다.
1238번 파티

데이크스트라 알고리즘은 따로 포스팅하여 정리할 예정이다.

데이크스트라는 BFS와 DP를 활용하는 알고리즘이다. 간단히 설명하자면 시작점부터 BFS를 수행하고 정점을 방문할 때마다 최단 경로를 DP로 갱신하는 것이다.

주의해야 하는 점은 최단 경로를 구해야하기 때문에 BFS의 순서를 확인해야 한다. 기존의 BFS 대로 수행하면 최단 경로가 아닐 때 정점을 방문할 수 있기 때문이다. 순서는 최단 거리가 작은 순이 된다.

따라서, 최단 거리를 기준으로 오름차순으로 정렬되는 힙(우선순위 큐)를 활용해야 한다.

최단 경로의 갱신은 어떻게 하면 될까? 경쟁하게 되는 두 경우는 다음과 같다.

기존의 최단 거리 (이전 BFS를 통해 갱신된 최단거리)

출발점부터 현재 정점까지의 최단거리 + 목적지까지의 거리

위와 같은 예제에서 1->2의 최단거리는

기존의 최단거리 (5)
출발점부터 현재까지(1) + 목적지까지(2)

이 둘을 비교해 최종적으로 3이 되는 것이다.

코드

package java_baekjoon;

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

public class prob1753 {
    // node 클래스
    static class vertex implements Comparable<vertex> {
        int num;
        int d_from_start;
        Queue<edge> next_v;

        public vertex(int num) {
            this.num = num;
            this.next_v = new LinkedList<>();
            this.d_from_start = Integer.MAX_VALUE;
        }

        public void add_next_vertex(edge next_v) {
            this.next_v.add(next_v);
        }

        @Override
        public int compareTo(vertex o) {
            return this.d_from_start - o.d_from_start;
        }
    }

    static class edge {
        int num;
        int distance;

        public edge(int num, int distance) {
            this.num = num;
            this.distance = distance;
        }
    }

    static vertex[] arr_vertex;
    // static boolean[] visited;
    static int V;
    static int E;
    static int start;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 노드 초기화
        V = Integer.parseInt(st.nextToken());
        arr_vertex = new vertex[V + 1];
        // visited = new boolean[V + 1];
        for (int i = 1; i <= V; i++) {
            arr_vertex[i] = new vertex(i);
        }

        E = Integer.parseInt(st.nextToken());

        start = Integer.parseInt(br.readLine());
        arr_vertex[start].d_from_start = 0;

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int v_1 = Integer.parseInt(st.nextToken());
            int v_2 = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            arr_vertex[v_1].add_next_vertex(new edge(v_2, distance));
        }

        bfs();

        ResultPrint();
    }

    static void bfs() {
        PriorityQueue<vertex> q = new PriorityQueue<>();

        q.add(arr_vertex[start]);

        while (!q.isEmpty()) {
            vertex now = q.poll();

            while (!now.next_v.isEmpty()) {
                edge next = now.next_v.poll();

                int d_from_start = arr_vertex[now.num].d_from_start + next.distance;

                if (arr_vertex[next.num].d_from_start > d_from_start) {
                    arr_vertex[next.num].d_from_start = d_from_start;
                }
                q.add(arr_vertex[next.num]);
            }
        }
    }

    static void ResultPrint() {
        for (int i = 1; i <= V; i++) {
            if (arr_vertex[i].d_from_start == Integer.MAX_VALUE) {
                System.out.println("INF");
                continue;
            }

            System.out.println(arr_vertex[i].d_from_start);
        }
    }
}