[백준] 9370번 - 미확인 도착지 (Gold 2)

문제 링크

백준 9370번 - 미확인 도착지 (Gold 2)

문제 설명

N개의 교차로와 이들 사이를 잇는 M개의 도로가 주어져 있다.
출발 지점 S와 가능한 T개의 목적지 후보들도 주어져 있다.
도로 한 개가 주어져 있는데 이 도로는 출발 지점 S와 목적지 사이의 최단 경로에 포함되어 있다.
이 때 위에서 주어진 T개의 목적지 후보들 중 가능한 것만을 출력하시오.

정답 코드 및 설명

주어진 도로가 G와 H를 잇는 도로라고 하자.
이 도로가 S에서 목적지 D까지 잇는 최단 경로에 포함되어 있다면, 두 가지 중 적어도 하나는 성립한다.

1. S에서 D까지 잇는 최단 경로 = S에서 G까지 가는 최단 경로 + 도로 G-H + H에서 D까지 가는 최단 경로
2. S에서 D까지 잇는 최단 경로 = S에서 H까지 가는 최단 경로 + 도로 G-H + G에서 D까지 가는 최단 경로

따라서 S, G, H를 시작점으로 하는 다익스트라 알고리즘을 통해 각 점에서 출발하는 최단 경로의 길이를 모두 구해두면 목적지 D가 가능한 후보인지 아닌지를 판별할 수 있게 된다.

코드로 구현하면 아래와 같다. 78~81행이 가능한 목적지인지 판별하는 부분에 해당한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ9370 {
    int n, s, g, h;
    int[][] adj;
    int[] x;

    void input(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken()) - 1;
        g = Integer.parseInt(st.nextToken()) - 1;
        h = Integer.parseInt(st.nextToken()) - 1;
        adj = new int[n][n];
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            adj[start][end] = adj[end][start] = Integer.parseInt(st.nextToken());
        }
        x = new int[t];
        for (int i = 0; i < t; i++) {
            x[i] = Integer.parseInt(br.readLine()) - 1;
        }
        Arrays.sort(x);
    }

    int[] Dijkstra(int start) {
        final int MAX = 200000000;
        int[] minDist = new int[n];
        class City implements Comparable<City> {
            final int city, dist;

            City(int city, int dist) {
                this.city = city;
                this.dist = dist;
            }

            @Override
            public int compareTo(City o) {
                return this.dist - o.dist;
            }
        }
        PriorityQueue<City> pq = new PriorityQueue<>();
        Arrays.fill(minDist, MAX);
        minDist[start] = 0;
        pq.add(new City(start, 0));
        while (!pq.isEmpty()) {
            City curr = pq.poll();
            if (minDist[curr.city] < curr.dist)
                continue;
            for (int i = 0; i < n; i++) {
                if (adj[curr.city][i] == 0) continue;
                if (adj[curr.city][i] + curr.dist < minDist[i]) {
                    minDist[i] = curr.dist + adj[curr.city][i];
                    pq.add(new City(i, minDist[i]));
                }
            }
        }
        return minDist;
    }

    void solve() {
        StringBuilder sb = new StringBuilder();
        int[] distFromS = Dijkstra(s);
        int[] distFromG = Dijkstra(g);
        int[] distFromH = Dijkstra(h);
        int distSG = distFromS[g];
        int distSH = distFromS[h];
        for (int curr : x) {
            if (distFromS[curr] - adj[g][h] == Math.min(distSG + distFromH[curr], distSH + distFromG[curr]))
                sb.append(curr + 1).append(' ');
        }
        System.out.println(sb);
    }

    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            input(br);
            solve();
        }
    }

    public static void main(String[] args) throws IOException {
        new BOJ9370().solution();
    }
}