[백준] 9370 미확인 도착지 - 자바

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

9370번: 미확인 도착지

문제 풀이

문제를 이해하는 데에만 10분은 걸린 것 같다. 필자처럼 문제 조차 이해하기 어려워 하는 사람이 있을 수 있으니 문제부터 간단하게 설명하도록 하겠다. 다음은 문제에 기재된 예시이다.

듀오라는 애가 s에서 시작하여 5, 6라는 목적지 중 최단경로로 진행했을 때 어디로 가는지 찾아야 한다. 듀오는 무조건 g-h 도로를 지난다고 할 때 g-h를 지나 목적지 후보를 가는 경로는 6번 목적지로 가능 방법밖에 없다. 왜냐면 5번을 가는 최단 경로는 g-h를 지나지 않고 바로 2-5로 가는 것이기 때문이다.

 

즉, 후보 목적지를 최단경로로 갈 때 g-h를 포함하는지를 묻는 문제이다.

이 문제는 경로를 쪼개서 생각해보면 쉽게 풀린다.

d[a,b]: a에서 b로 가는 최단 경로 비용이고, 만약 [2,6]의 경로중 g=3, h=1을 포함한다고 하면
d[2,6] = d[2, 1] + d[1, 3] + d[3, 6]로 계산된다.

하지만 위 그림은 우리가 눈으로 보고 2다음 1, 1다음 3, 3다음 6을 바로 확인할 수 있지만 시작 교차로에서 g를 먼저 만날지, h를 만날지 모른다.

따라서 두 경우의 수를 모두 비교해주면 된다. 둘 중 하나라도 같은 게 있다면 g-h 도로를 포함한 것이 된다.

물론 path1, path2 중 적은 비용의 도로가 realPath가 될 것이지만 필자는 ||를 사용했다

for (int candi : candidate) {
    int path1 = dijkstra(start, g) + ghDist + dijkstra(h, candi);
    int path2 = dijkstra(start, h) + ghDist + dijkstra(g, candi);
    int realPath = dijkstra(start, candi);

    if (path1 == realPath || path2 == realPath)
        result.add(candi);
}

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Road {
    int idx;
    int distance;

    public Road(int idx, int distance) {
        this.idx = idx;
        this.distance = distance;
    }
}

public class b9370 {
    static int V,E,T,start,g, h;
    static List<List<Road>> graph = new ArrayList<>();
    static int[] d;
    static int[] candidate;
    static List<Integer> result;

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

        StringTokenizer st;
        for (int tc = 0; tc < testCase; tc++) {
            result = new ArrayList<>();

            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            T = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            //init()
            graph.clear();
            for (int i = 0; i < V + 1; i++) {
                graph.add(new ArrayList<>());
            }
            int ghDist = 0;
            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 dist = Integer.parseInt(st.nextToken());

                graph.get(from).add(new Road(to, dist));
                graph.get(to).add(new Road(from, dist));

                if ((from == g && to == h )|| (from == h && to == g))
                    ghDist = dist;
            }
            candidate = new int[T];
            for (int i = 0; i < T; i++) {
                candidate[i] = Integer.parseInt(br.readLine());
            }

            for (int candi : candidate) {
                int path1 = dijkstra(start, g) + ghDist + dijkstra(h, candi);
                int path2 = dijkstra(start, h) + ghDist + dijkstra(g, candi);
                int realPath = dijkstra(start, candi);

                if (path1 == realPath || path2 == realPath)
                    result.add(candi);
            }

            // 정렬 후 출력
            Collections.sort(result);
            result.forEach(i -> System.out.print(i + " "));
        }

    }

    static int dijkstra(int start, int end) {
        d = new int[V + 1];
        Arrays.fill(d, Integer.MAX_VALUE);

        Queue<Road> pq = new PriorityQueue<>((n1, n2) -> n1.distance - n2.distance);
        pq.offer(new Road(start, 0));
        d[start] = 0;

        while (!pq.isEmpty()) {
            Road now = pq.poll();
            int nowDist = now.distance;
            int nowIdx = now.idx;

            if (d[nowIdx] < nowDist) continue; // 굳이 안 써줘도 되지만 d[nowIdx]로 이미 최솟값을 가지고 있는데 더 큰 값의 nowDist가 밑의
            // for문(최소 비용 업데이트 로직)을 실행해봤자 최소 비용을 가질 수 없기 때문에 불필요한 연산을 제거하기 위함이다.

            for (Road adj : graph.get(nowIdx)) {
                int adjIdx = adj.idx;
                int cost = d[nowIdx] + adj.distance;

                if (d[adjIdx] > cost) {
                    d[adjIdx] = cost;
                    pq.offer(new Road(adjIdx, cost));
                }
            }
        }
        return d[end];
    }
}