[백준 P9370] 미확인 도착지 Java

P9370 미확인 도착지

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

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

출력값

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

4 5
6

알고리즘

취익.

 

요원으로서 문제를 정독해보면 요구사항은 다음과 같다.

1. 한 쌍의 예술가는 S에서 출발했다.
2. 목적지 후보들 중 하나가 그들의 목적지이다.
3. 목적지까지 최단거리로 간다.
4. 예술가는 g, h 교차로 사이를 지나갔다.
5. 목적지 후보들 중 불가능한 경우를 제외한 목적지를 공백으로 분리시키고 오름차순의 정수로 출력한다.

문제의 요구사항을 한 문장으로 표현해보겠다. S부터 목적지 후보지들 사이에서 g, h를 경유하는 모든 목적지를 오름차순으로 출력하라.

하나의 출발점에서 다른 정점들에 대한 최단 경로를 구해야 하므로 다익스트라 알고리즘을 사용했다. 여기서 키 포인트는 g, h를 거치는 부분만 체크해야 한다는 점이다. 사실 이 부분은 아이디어만 떠오른다면 쉽게 해결할 수 있다. 입력받는 간선에 2를 곱하여 모든 간선을 짝수로 만들어 저장한다. 이때, g-h 간선만 2를 곱한 값에서 1을 빼어 홀수로 저장한다.

이런 의문이 생길 수 있다. 1을 빼면 그래프 전체 가중치에 문제가 생기지 않을까? g-h와 다른 임의의 간선(a)을 비교해보자. 총 3가지 경우의 수가 나올 수 있다.

 

• g-h경유 간선이 임의의 간선(a)보다 작은 경우
  • g-h경유 간선이 a보다 작다면 2 * (g-h) < 2 * a 가 성립한다. 이때 2 * (g - h) - 1 < 2 * a가 성립하므로 결과에 영향을 주지 않는다.
• g-h경유 간선이 임의의 간선(a)보다 큰 경우
  • g-h경유 간선이 a보다 크다면 2 * (g-h) > 2 * a 가 성립한다. 이때 2 * (g - h) - 1 > 2 * a가 성립하는지 확인이 필요하다.
  • 2(g - h - 0.5) > 2 * a 에서 g - h - 0.5 > a 를 얻을 수 있다.
  • 가중치는 정수값을 가지므로 g - h > a 가 성립한다면 g - h에 1보다 작은 0.5를 뺀 값도 a 보다 클 수 밖에 없다. 따라서 결과에 영향을 주지 않는다.
• g-h경유 간선이 임의의 간선(a)과 같은 경우
  • 마지막으로 g-h경유 간선이 임의의 간선(a)와 같은 경우이다.
  • 이 경우에는 2 * (g - h) == 2 * a 가 성립한다.
  • 두 값이 같을 때 요원이 해야하는 선택은 g-h쪽으로 탐색을 하는 것이다. 그 이유는 애초에 g-h를 경유하지 않는다면 문제의 조건으로 인해 정답이 될 수 없기 때문이다.
  • 따라서 g - h와 a 가 같은 경우에도 g - h에 1을 빼도 괜찮다. 요원은 항상 g - h를 거치는 경우를 선택할 것이기 때문이다.

이렇게 짝수와 홀수로 나누는 것을 통해 얻는 이점이 무엇일까? 우리는 목적지에 도달하는 최종 최단 거리 값만 보고도 이 경로에 g-h가 포함되었는지 한 번에 확인할 수 있다. 그 이유는 g-h를 경유했다면 최단 거리 값이 홀수일 수 밖에 없기 때문이다.

 

취익. 아래는 전체 코드이다.

코드

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

public class Main {
    static final int INF = Integer.MAX_VALUE - 1;

    static int T;
    static int n, m, t;
    static int s, g, h;

    static List<int[]>[] graph;
    static int[] path;

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

        T = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());

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

            graph = new ArrayList[n + 1];
            path = new int[n + 1];

            for (int i = 1; i <= n; i++) {
                graph[i] = new ArrayList<>();
            }
            Arrays.fill(path, INF);

            for (int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int weight = 2 * Integer.parseInt(st.nextToken());

                if ((from == g && to == h) || (from == h && to == g)) {
                    weight -= 1;
                }

                graph[from].add(new int[] {to, weight});
                graph[to].add(new int[] {from, weight});
            }

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

            for (int i = 0; i < t; i++) {
                //g - h 길을 거치는지 확인
                int possibleEnd = Integer.parseInt(br.readLine());
                if (path[possibleEnd] % 2 != 0) {
                    result.add(possibleEnd);
                }
            }

            Collections.sort(result);
            for (Integer n : result) {
                sb.append(n).append(" ");
            }
            sb.append("\\n");
        }

        System.out.print(sb);
    }

    public static void findPath(int start) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[1] - b[1];
        });
        path[start] = 0;
        pq.add(new int[] {start, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int curPos = current[0];
            int curWeight = current[1];

            if (curWeight > path[curPos]) continue;

            for (int[] next: graph[curPos]) {
                int cost = curWeight + next[1];

                if (path[next[0]] > cost) {
                    path[next[0]] = cost;
                    pq.add(new int[]{next[0], cost});
                }
            }
        }
    }
}