b.9370 미확인 도착지

 

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

 

 

 

📌 자바(Java)로 푸는 미확인 도착지 문제 - 백준 9370 🚗📍

 

---

🔎 문제 개요

 

백준 9370번 - 미확인 도착지 문제입니다.

출발지(S)에서 목적지 후보들 중,

특정 도로(G-H)를 반드시 지나면서 도달할 수 있는 목적지를 찾아야 합니다.

다익스트라 알고리즘을 활용하여 최단 경로를 구하는 문제입니다.

 

---

💡 예제 입력

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

💡 예제 출력

6
5 6

➡ 목적지 후보 중 특정 도로(G-H)를 지나면서 도달할 수 있는 곳을 출력

 

---

🛠 알고리즘 접근 방식

 

이 문제를 해결하기 위해 다익스트라 최단 경로 알고리즘(Dijkstra) 을 활용합니다.

 

✏️ 주요 고려 사항

 

✔ 다익스트라 알고리즘을 3번 실행

✔ 출발지(S)에서 모든 정점까지 최단 거리 계산

✔ G, H 정점에서 각각 다익스트라 실행하여 경유 거리 계산

✔ 출발지 → 목적지 거리와, 특정 도로(G-H)를 경유한 두 가지 거리 비교

✔ 두 거리 값이 같다면 해당 목적지는 조건을 만족하는 것

 

---

🔹 Java 코드 해설

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

public class b9370 {

    static int T, N, M, D; // 교차로 수, 도로 수, 목적지 후보 수
    static int S, G, H;   // 출발지, G와 H 사이의 도로를 지나감
    static HashMap<Integer, ArrayList<Node>> graph;

    static class Node implements Comparable<Node> {
        int spot;
        int distance;

        public Node(int spot, int distance) {
            this.spot = spot;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }

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

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = stringToInteger(st.nextToken());
            M = stringToInteger(st.nextToken());
            D = stringToInteger(st.nextToken());

            st = new StringTokenizer(br.readLine());
            S = stringToInteger(st.nextToken());
            G = stringToInteger(st.nextToken());
            H = stringToInteger(st.nextToken());

            graph = new HashMap<>();
            for (int i = 1; i <= N; i++) graph.put(i, new ArrayList<>());

            int ghDistance = 0;
            for (int m = 0; m < M; m++) {
                st = new StringTokenizer(br.readLine());
                int a = stringToInteger(st.nextToken());
                int b = stringToInteger(st.nextToken());
                int d = stringToInteger(st.nextToken());
                graph.get(a).add(new Node(b, d));
                graph.get(b).add(new Node(a, d));

                if ((a == G && b == H) || (a == H && b == G)) ghDistance = d;
            }

            int[] distFromS = dijkstra(S);
            int[] distFromG = dijkstra(G);
            int[] distFromH = dijkstra(H);

            List<Integer> results = new ArrayList<>();
            for (int i = 0; i < D; i++) {
                int target = stringToInteger(br.readLine());
                int directDist = distFromS[target];

                // G-H 간선을 경유하는 두 가지 경로 비교
                int viaGH = distFromS[G] + ghDistance + distFromH[target];
                int viaHG = distFromS[H] + ghDistance + distFromG[target];

                if (directDist == viaGH || directDist == viaHG) {
                    results.add(target);
                }
            }

            Collections.sort(results);
            StringBuilder sb = new StringBuilder();
            for (int res : results) sb.append(res).append(" ");
            System.out.println(sb);
        }
    }

    private static int[] dijkstra(int s) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int curSpot = cur.spot;
            int curDist = cur.distance;

            if (dist[curSpot] < curDist) continue;

            for (Node next : graph.get(curSpot)) {
                int newDist = curDist + next.distance;
                if (newDist < dist[next.spot]) {
                    dist[next.spot] = newDist;
                    pq.add(new Node(next.spot, newDist));
                }
            }
        }
        return dist;
    }

    private static int stringToInteger(String s) {
        return Integer.parseInt(s);
    }
}

 

 

---

🔍 코드 설명

 

📌 1. 그래프 입력 및 초기화

graph = new HashMap<>();
for (int i = 1; i <= N; i++) graph.put(i, new ArrayList<>());

int ghDistance = 0;
for (int m = 0; m < M; m++) {
    int a = stringToInteger(st.nextToken());
    int b = stringToInteger(st.nextToken());
    int d = stringToInteger(st.nextToken());
    graph.get(a).add(new Node(b, d));
    graph.get(b).add(new Node(a, d));

    if ((a == G && b == H) || (a == H && b == G)) ghDistance = d;
}

• 인접 리스트(graph)를 사용하여 그래프를 저장

• 무방향 그래프이므로 양쪽(a-b & b-a) 추가

• 특정 도로(G-H)의 거리(ghDistance) 저장

 

---

📌 2. 다익스트라 실행

int[] distFromS = dijkstra(S);
int[] distFromG = dijkstra(G);
int[] distFromH = dijkstra(H);

• 출발지(S), G, H에서 각각 다익스트라 실행

• 최단 거리 배열(dist[])을 생성하여 저장

 

---

📌 3. 목적지 후보 필터링

for (int i = 0; i < D; i++) {
    int target = stringToInteger(br.readLine());
    int directDist = distFromS[target];

    int viaGH = distFromS[G] + ghDistance + distFromH[target];
    int viaHG = distFromS[H] + ghDistance + distFromG[target];

    if (directDist == viaGH || directDist == viaHG) {
        results.add(target);
    }
}

• 출발지 → 목적지 거리와 G-H를 지나가는 거리 비교

• 경로가 동일하면 results 리스트에 추가

 

---

📌 4. 최종 결과 출력

Collections.sort(results);
StringBuilder sb = new StringBuilder();
for (int res : results) sb.append(res).append(" ");
System.out.println(sb);

• 결과를 오름차순 정렬 후 출력

 

---

🏆 정리

 

✅ 핵심 포인트

 

✔ 다익스트라 알고리즘을 3번 실행하여 경유 경로 확인

✔ 출발지 → 목적지 거리와 G-H 경유 경로 비교

✔ O((N + M) log N) 복잡도로 최적화된 경로 탐색

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊