[BOJ/Java] 9370. 미확인 도착지

📌 [BOJ/Java] 9370. 미확인 도착지

• 문제 링크

---

💡 문제 해석

어떤 도시에서 출발하여 목적지 후보들 중 특정 경로를 반드시 거쳐 도착하는 경우를 찾아야 한다.
즉, 출발지에서 특정 도로를 지나 목적지에 도달할 수 있는지를 확인하는 문제이다.

🚗 주어진 정보:

• n: 교차로(노드) 개수
• m: 도로(간선) 개수
• t: 목적지 후보 개수
• s: 출발지
• g, h: 반드시 지나야 하는 도로의 두 정점
• m개의 간선 정보 (양방향, 가중치 포함)
• t개의 목적지 후보

🚀 목표:

• s → 목적지로 가는 최단 경로 중 g-h 도로를 반드시 지나야 하는 경우 찾기
• 가능한 목적지들을 오름차순 출력

예제 입력:

2
6 9 2
2 3 6
1 2 1
1 3 2
2 4 4
2 5 3
3 6 5
4 6 2
5 6 3
4
6

 

위의 예제에서 2 → 6으로 갈 때 3-6을 반드시 거쳐야 하는 경우를 고려하여 목적지를 찾는다.

---

📝 풀이 과정

1️⃣ 다익스트라 (Dijkstra) 알고리즘 활용

🔹 출발점에서 각 노드까지의 최단 경로를 구한다.
🔹 g-h 도로를 지나는 경우와 그렇지 않은 경우를 따로 고려해야 한다.

2️⃣ 최단 거리 계산 (3번의 다익스트라 실행)

✅ s에서 모든 노드까지의 최단 거리
✅ g에서 모든 노드까지의 최단 거리
✅ h에서 모든 노드까지의 최단 거리

3️⃣ 목적지 후보 판별

💡 s → 목적지의 최단 경로가 s → g → h → 목적지 또는 s → h → g → 목적지 경로와 일치하는지 확인

---

💻 코드 (Java)

import java.util.*;

public class Main {
    static final int INF = 200000000;
    static int n, m, t, s, g, h;
    static List<Node>[] graph;
    static int[] targets;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 테스트 케이스 개수

        while (T-- > 0) {
            n = sc.nextInt();
            m = sc.nextInt();
            t = sc.nextInt();
            s = sc.nextInt();
            g = sc.nextInt();
            h = sc.nextInt();

            graph = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) {
                graph[i] = new ArrayList<>();
            }

            int ghDist = 0;  // g-h 간선의 거리 저장
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int d = sc.nextInt();
                graph[a].add(new Node(b, d));
                graph[b].add(new Node(a, d));
                if ((a == g && b == h) || (a == h && b == g)) {
                    ghDist = d;
                }
            }

            targets = new int[t];
            for (int i = 0; i < t; i++) {
                targets[i] = sc.nextInt();
            }

            // 3번의 다익스트라 실행
            int[] distFromS = dijkstra(s);
            int[] distFromG = dijkstra(g);
            int[] distFromH = dijkstra(h);

            List<Integer> result = new ArrayList<>();

            for (int target : targets) {
                int directDist = distFromS[target];
                int viaG = distFromS[g] + ghDist + distFromH[target];
                int viaH = distFromS[h] + ghDist + distFromG[target];

                if (directDist == viaG || directDist == viaH) {
                    result.add(target);
                }
            }

            Collections.sort(result);
            for (int x : result) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }

    static int[] dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int now = cur.index, cost = cur.distance;

            if (dist[now] < cost) continue;

            for (Node next : graph[now]) {
                int newCost = cost + next.distance;
                if (newCost < dist[next.index]) {
                    dist[next.index] = newCost;
                    pq.offer(new Node(next.index, newCost));
                }
            }
        }
        return dist;
    }

    static class Node implements Comparable<Node> {
        int index, distance;
        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }
}

---

⏱ 시간 복잡도 분석

• 다익스트라 알고리즘: O((V + E) log V)
• 3번의 다익스트라 실행: O(3 * (V + E) log V)
• n ≤ 2000, m ≤ 50,000이므로 충분히 가능

---

🧐 느낀 점

🌟 다익스트라를 활용하는 응용 문제였다.
➡️ 기본적인 다익스트라 알고리즘을 3번 실행해야 하는 것이 핵심이었다.
➡️ 특정 경로를 반드시 지나야 하는 조건을 처리하는 방법을 익힐 수 있었다.

🔍 디테일한 부분에서 실수하기 쉬웠다.
✅ g-h 간선의 거리를 정확히 저장해야 했다.
✅ 다익스트라 실행 후, 후보 목적지를 판별하는 로직이 중요했다.
✅ 최종적으로 오름차순 출력을 잊지 않도록 주의해야 했다.

🚀 전체적으로 그래프 탐색에 대한 개념을 탄탄하게 다질 수 있는 문제였다! 😊