[백준] 1504번 : 특정한 최단 경로(JAVA)

인간몽쉘김통통·2023년 11월 10일

그래프 탐색 백준 알고리즘

백준

목록 보기

11/92

문제

이해

방향성 없는 그래프에서 최단 경로를 구해야 한다. 단, 입력받는 특정한 2개의 노드를 무조건 지나야 한다.

출발 노드는 1, 도착 노드는 N이 된다.

노드의 개수 N (2 <= N <= 800)
간선의 개수 E (0 <= E <= 200,000)

접근

이전 다익스트라 최단 경로 문제와 유사하다. 차이점은 본 문제는 방향성이 없는 그래프가 주어진다는 것이고 무조건 경유해야하는 노드 2개가 존재한다는 점이다.

우선, 방향성이 없는 그래프의 간선 정보를 저장해야한다. 이전 문제에서 방향성이 있는 그래프의 경우 A -> B와 같이 한 쪽으로의 이동만이 가능했기 때문에 도착지점과 비용만 저장하면 됐지만 본 문제의 경우 A -> B, B -> A와 같이 양방향 이동이 가능하기 때문에 간선 정보를 저장할 때 2개 씩 저장해야 한다.

아래와 같이 무방향 그래프는 2개의 간선으로 연결된 방향 그래프로 이해할 수 있기 때문이다.

다음은 조건에 따른 최단 경로를 구하는 방법이다.

1에서 출발해 N에 도착하는데 임의의 노드 v1, v2를 경유해야 한다.

그렇다면 다음과 같은 2가지 경로가 존재할 수 있다.
1 > v1 > v2 > N
1 > v2 > v1 > N

따라서, 두 경로에 대해 최단 경로를 구해서 값을 비교한 뒤 더 작은 값을 선택하면 전체의 최단 경로를 구할 수 있다.

각 경우는 어떻게 구하면 될까? 당연하게도 문제를 나눠서 생각하면 된다.

첫번째 경로의 경우,
1 > v1 의 최단 경로 +
v1 > v2 의 최단 경로 +
v2 > N 의 최단 경로 = 전체의 최단 경로
가 성립한다.

따라서, 각 출발점(1, v1, v2)에 대해서 다익스트라 알고리즘을 통해 최단 경로를 구하고 합하여 계산할 수 있게 된다.

코드

package java_baekjoon;

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

public class prob1504 {
    static class LinkedVertex implements Comparable<LinkedVertex> {
        int vertex;
        int distance;

        public LinkedVertex(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(LinkedVertex o) {
            return this.distance - o.distance;
        }
    }
    static final int INF = 200000000;
    static ArrayList<LinkedVertex>[] vertex_info;
    static int num_N;
    static int num_V;
    static int stop_overA;
    static int stop_overB;
    static int ans;

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

        num_N = Integer.parseInt(st.nextToken());
        num_V = Integer.parseInt(st.nextToken());

        vertex_info = new ArrayList[num_N + 1];

        for (int i = 0; i < num_N + 1; i++) {
            vertex_info[i] = new ArrayList<>();
        }

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

            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            vertex_info[nodeA].add(new LinkedVertex(nodeB, distance));
            vertex_info[nodeB].add(new LinkedVertex(nodeA, distance));
        }

        st = new StringTokenizer(br.readLine());
        stop_overA = Integer.parseInt(st.nextToken());
        stop_overB = Integer.parseInt(st.nextToken());

        int dijkstra_from_1[] = dijkstra(1);
        int dijkstra_from_A[] = dijkstra(stop_overA);
        int dijkstra_from_B[] = dijkstra(stop_overB);

        int sum_of_caseA = dijkstra_from_1[stop_overA] + dijkstra_from_A[stop_overB]
        + dijkstra_from_B[num_N];
        int sum_of_caseB = dijkstra_from_1[stop_overB] + dijkstra_from_B[stop_overA]
        + dijkstra_from_A[num_N];

        if(sum_of_caseA >= INF && sum_of_caseB >= INF){
            System.out.println(-1);
        }else{
            System.out.println(Math.min(sum_of_caseA, sum_of_caseB));
        }
    }

    static int[] dijkstra(int start_node) {
        int min_distance[] = new int[num_N + 1];
        Arrays.fill(min_distance, INF);
        boolean visited[] = new boolean[num_N + 1];

        Queue<LinkedVertex> q = new PriorityQueue<>();

        q.add(new LinkedVertex(start_node, 0));
        min_distance[start_node] = 0;

        while (!q.isEmpty()) {
            LinkedVertex v = q.poll();

            int to = v.vertex;

            if (visited[to]) {
                continue;
            }
            visited[to] = true;

            for (LinkedVertex next : vertex_info[to]) {
                int distance_to_next = min_distance[to] + next.distance;

                if (distance_to_next <= min_distance[next.vertex]) {
                    min_distance[next.vertex] = distance_to_next;
                    q.add(new LinkedVertex(next.vertex, min_distance[next.vertex]));
                }
            }
        }

        return min_distance;
    }
}