[백준] BOJ_9370 미확인 도착지 JAVA

BOJ_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개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

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

예제 입&출력

소스코드

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

public class Main {
    private static int n, m, t;
    private static int s, g, h;
    private static List<Node>[] lists;
    private static int[] dist;
    private static boolean[] visit;

    private static List<Integer> destinations;
    private static final int INF = 50_000_000;

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

        int tc = Integer.parseInt(br.readLine());

        while ((tc--) > 0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 정점
            m = Integer.parseInt(st.nextToken()); // 간선
            t = Integer.parseInt(st.nextToken()); // 목적지 갯수

            lists = new ArrayList[n + 1];
            for (int i = 0; i <= n; i++) {
                lists[i] = new ArrayList<>();
            }
            dist = new int[n + 1];
            visit = new boolean[n + 1];

            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken()); // 시작점
            g = Integer.parseInt(st.nextToken()); // 무조건 지나가는 정점 1
            h = Integer.parseInt(st.nextToken()); // 무조건 지나가는 정점 2

            while ((m--) > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                /**
                 * 무조건 지나가는 정점에 해당하는 간선이면 가중치를 홀수로,
                 * 그렇지 않다면 가중치를 짝수로
                 */
                if ((a == g && b == h) || (a == h && b == g)) {
                    lists[a].add(new Node(b, cost * 2 - 1));
                    lists[b].add(new Node(a, cost * 2 - 1));
                } else {
                    lists[a].add(new Node(b, cost * 2));
                    lists[b].add(new Node(a, cost * 2));
                }
            }

            destinations = new ArrayList<>(t);
            while ((t--) > 0) {
                destinations.add(Integer.parseInt(br.readLine()));
            }

            /**
             * 다익스트라 알고리즘을 통해서 시작점으로부터의 최단경로의 dist[]를 구하고
             * 목적지 후보가 되는 곳들의 dist[목적지]가 홀 수 일때 정답
             */
            getAns(s);

            Collections.sort(destinations);

            for (Integer destination : destinations) {
                if(dist[destination] % 2 != 0) System.out.println(destination);
            }
        }
    }

    private static void getAns(int s) {
        Arrays.fill(dist, INF);
        Arrays.fill(visit, false);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s, 0));
        dist[s] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int cur = node.next;

            if (!visit[cur]) visit[cur] = true;

            for (Node nNode : lists[cur]) {
                if (!visit[nNode.next] && dist[nNode.next] > dist[cur] + nNode.cost) {
                    dist[nNode.next] = dist[cur] + nNode.cost;
                    pq.add(new Node(nNode.next, dist[nNode.next]));
                }
            }
        }
    }

    private static class Node implements Comparable<Node> {
        int next;
        int cost;

        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}

Comment

• 전형적인 다익스트라 알고리즘이지만 가중치에 대한 조건 부여를 생각하기가 오래 걸렸다.
• 코딩에 대한 이해는 주석을 통해 알아보자.