[백준 9370] 미확인 도착지 - Java 문제풀이

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

 

출력

테스트 케이스마다

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

풀이

접근법

1. 일단 출발지, g, h 로부터의 거리를 모두 구해야하니까 dijstra를 이용하면 되겠다.
2. 거리를 최단거리로 이동하기 위해선 일단, 기준점인 출발지와 g, h를 경유해서 간 거리를 비교하면 될 것 같다.
3. g와 h는 순서가 없으니까, 출발지 - g - h - 도착지와 출발지 - h - g - 도착지 중에 최단거리와 출발지 - 도착지를 비교하면 될 것 같다.

 

코드

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

public class Main {
    private static List<int[]>[] list;
    private static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC=Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int tc=1;tc<=TC;tc++) {
            st = new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            int M=Integer.parseInt(st.nextToken());
            int T=Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int s=Integer.parseInt(st.nextToken());
            int g=Integer.parseInt(st.nextToken());
            int h=Integer.parseInt(st.nextToken());
            int gToH = 0;
            list = new List[N+1];
            for(int i=0;i<=N;i++) list[i] = new ArrayList<>();
            for(int i=0;i<M;i++) {
                st = new StringTokenizer(br.readLine());
                int u=Integer.parseInt(st.nextToken());
                int v=Integer.parseInt(st.nextToken());
                int w=Integer.parseInt(st.nextToken());
                list[u].add(new int[]{v, w});
                list[v].add(new int[]{u, w});
                if ((u == g && v == h) || (v == g && u == h)) gToH = w;
            }
            
            List<Integer> dest = new ArrayList<>();
            for(int i=0;i<T;i++) dest.add(Integer.parseInt(br.readLine()));
            
            // 1. 일단 출발지, g, h 로부터의 거리를 모두 구해야하니까 dijstra를 이용하면 되겠다.            
            int[][] dij = new int[3][];
            dij[0] = dijstra(s);
            dij[1] = dijstra(g);
            dij[2] = dijstra(h);
            List<Integer> ans = new ArrayList<>();
            // 2. 거리를 최단거리로 이동하기 위해선 일단, 기준점인 출발지와 g, h를 경유해서 간 거리를 비교하면 될 것 같다.
            // 3. g와 h는 순서가 없으니까, 출발지 - g - h - 도착지와 
            // 출발지 - h - g - 도착지 중에 최단거리와 출발지 - 도착지를 비교하면 될 것 같다.
            for(int d : dest) {
                int min = -1;
                if (dij[0][g] != -1 && dij[2][d] != -1) min = dij[0][g] + gToH + dij[2][d];
                if (dij[0][h] != -1 && dij[1][d] != -1) min = min == -1 ? dij[0][h] + gToH + dij[1][d]: Math.min(min, dij[0][h] + gToH + dij[1][d]);
                if (min != -1 && min == dij[0][d]) ans.add(d);
            }
            ans.sort(Comparator.naturalOrder());
            for(int num : ans) sb.append(num).append(" ");
            sb.append("\n");
        }
        System.out.println(sb);
    }
    private static int[] dijstra(int start) {
        int[] dij = new int[N+1];
        Arrays.fill(dij, -1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        pq.add(new int[]{start, 0});

        while(!pq.isEmpty()) {
            int[] now = pq.poll();
            if (dij[now[0]] != -1) continue;
            dij[now[0]] = now[1];
            for(int[] nxt : list[now[0]]) {
                if (dij[nxt[0]] != -1) continue;
                pq.add(new int[]{nxt[0], now[1] + nxt[1]});
            }
        }

        return dij;
    }
}

 

왜인지 중간에 문제를 잘못읽어서 40분이나 걸렸다.. 역시 그래프문제는 그래프를 그려가면서 푸는게 좋은 것 같다 !!