[Java] 백준 9370. 미확인 도착지

📌 문제 링크 - https://www.acmicpc.net/problem/9370

 

 

---

 

 

 

 

 

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

 

 

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

 

 

 

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

 

 

 

---

 

 

풀이

배열 3개를 사용하여 최단 거리를 구해준다.

 

• sCost : 출발지 S에서 각 도시로의 최단 거리.
• gCost : 교차로 G에서 각 도시로의 최단 거리.
• hCost : 교차로 H에서 각 도시로의 최단 거리.

 

이후 목적지 후보들 중에서 G와 H의 사이에 있는 도로를 지나칠 수 있는지 확인해준다. 

    for(int city : candidate) {
        int gToH = sCost[G] + gCost[H] + hCost[city];
        int hToG = sCost[H] + hCost[G] + gCost[city];

        int min = Math.min(gToH, hToG);

        if(min == sCost[city]) ans.append(city).append(' ');
    }

 

• gToH : G에서 H로 지나가는 경로. S -> G -> H -> 목적지 후보 도시
• hToG : H에서 G로 지나가는 경로. S -> H -> G -> 목적지 후보 도시

 

둘 중 더 적게 걸리는 경로가 시작 도시에서 해당 도시에 가는 최단 경로와 동일하다면 해당 목적지는 유효한 것이다.

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/9370
public class Main_9370 {
    private static final int INF = 1_000_000_000;
    private static int N; // 교차로 개수
    private static int S, G, H; // 예술가들의 출발지, 지나간 도로(G -> H)
    private static List<List<int[]>> list; // 도로 정보
    private static int[] candidate; // 목적지 후보


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

        while(tc-- > 0) {
            init(br);
            getTarget(ans);
        }

        System.out.print(ans);
    }//main


    private static void getTarget(StringBuilder ans) {
        int[] sCost = dijkstra(S); // S -> 각 도시 최단 거리
        int[] gCost = dijkstra(G); // G -> 각 도시 최단 거리
        int[] hCost = dijkstra(H); // H -> 각 도시 최단 거리

        // 가능한 목적지 탐색
        for(int city : candidate) {
            int gToH = sCost[G] + gCost[H] + hCost[city];
            int hToG = sCost[H] + hCost[G] + gCost[city];

            int min = Math.min(gToH, hToG);

            if(min == sCost[city]) ans.append(city).append(' ');
        }

        ans.append('\n');
    }//getTarget


    private static int[] dijkstra(int start) {
        Queue<Integer> q = new LinkedList<>();
        int[] minCost = new int[N+1];
        Arrays.fill(minCost, INF);
        minCost[start] = 0;

        q.offer(start);

        while(!q.isEmpty()) {
            int cur = q.poll();

            for(int[] next : list.get(cur)) {
                int nextNode = next[0];
                int nextDist = minCost[cur] + next[1];

                if(minCost[nextNode] > nextDist) {
                    minCost[nextNode] = nextDist;
                    q.offer(nextNode);
                }
            }
        }

        return minCost;
    }//dijkstra


    private static void init(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()); // 목적지 후보 개수

        // 출발지, 지나간 도로(G -> H)
        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken()); // 출발지
        G = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        candidate = new int[T]; // 목적지 후보
        list = new ArrayList<>(N+1); // 도로 정보

        for(int i=0; i<=N; i++) {
            list.add(new ArrayList<>());
        }

        // M개의 각 줄마다 3개의 정수 a, b, d가 주어진다
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            // a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            list.get(a).add(new int[] {b, d});
            list.get(b).add(new int[] {a, d});
        }

        // T개의 각 줄마다 정수 x가 주어지는데, T개의 목적지 후보들을 의미
        for(int i=0; i<T; i++) {
            int x = Integer.parseInt(br.readLine());
            candidate[i] = x;
        }

        Arrays.sort(candidate);
    }//init


}//class