[BaekJoon] 9370 미확인 도착지 (Java)

1.  문제 링크

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

2.  문제

요약

• 한 도시의 거리들을 이동하고 있는 한 서커스 예술가 한 쌍은 s지점에서 출발합니다.
• 그들의 목적지가 될 도시들의 후보들을 갖고 있습니다.
• 그들은 목적지까지 우회하지 않고 최단거리로 갑니다.
• 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈습니다.
• 이 듀오가 어디로 가고 있는 것인지 알아내는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 테스트 케이스 T가 주어지고 두 번째 줄부터 T개의 줄에 테스트 케이스가 주어집니다.
  • 각 테스트 케이스의 첫 번째 줄에 2보다 크거나 같고 2,000보다 작거나 같은 정수 n, 1보다 크거나 같고 50,000보다 작거나 같은 정수 m, 1보다 크거나 같고 100보다 작거나 같은 정수 t가 주어집니다.
    • n은 교차로의 개수, m은 교차로의 개수, t는 목적지 후보의 개수입니다.
    • 각 테스트 케이스의 두 번째 줄에 1보다 크거나 같고 n보다 작거나 같은 3개의 정수 s, g, h가 주어집니다.
    • s는 예술가의 출발지이고, g, h는 문제에 있는 지나간 교차로와 관련된 값입니다.
  • 각 테스트 케이스의 세 번째 줄부터 m개의 줄에 각 줄마다 1보다 크거나 같고 b보다 작은 정수 a, a보다 크고 n보다 작거나 같은 정수 b, 1보다 크거나 같고 1,000보다 작거나 같은 정수 d가 주어집니다.
    • a와 b 사이에 길이가 d인 양방향 도로가 있다는 뜻입니다.
  • 다음 줄부터 t개의 줄에 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미합니다. t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않습니다.
  • 교차로 사이에 도로는 많아봐야 1개입니다.
  • m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재합니다.
  • 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부입니다.
• 출력: 각 테스트 케이스마다 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력합니다.

3.  소스코드

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

public class Main {
    static Reader scanner = new Reader();
    static StringBuilder sb = new StringBuilder();

    static int n, m, t, s, g, h;
    static int[] destinations;
    static HashMap<Integer, ArrayList<Edge>> map;
    static int pastEdgeWeight;

    static void input() {
        n = scanner.nextInt(); // 교차로 개수
        m = scanner.nextInt(); // 도로 개수
        t = scanner.nextInt(); // 목적지 후보 개수
        destinations = new int[t];

        s = scanner.nextInt(); // 출발지
        g = scanner.nextInt(); // 예술가들이 지난 교차로 사이 도로의 교차로1
        h = scanner.nextInt(); // 예술가들이 지난 교차로 사이 도로의 교차로2

        map = new HashMap<>();

        for(int edge = 0; edge < m; edge++) {
            int a = scanner.nextInt(), b = scanner.nextInt(), d = scanner.nextInt();

            if(!map.containsKey(a))
                map.put(a, new ArrayList<>());
            if(!map.containsKey(b))
                map.put(b, new ArrayList<>());

            map.get(a).add(new Edge(b, d));
            map.get(b).add(new Edge(a, d));

            if((a == g && b == h) || (a == h && b == g))
                pastEdgeWeight = d;
        }

        for(int destination = 0; destination < t; destination++)
            destinations[destination] = scanner.nextInt();
    }

    static void solution() {
        int[] startDist = dijkstra(s);
        int[] inter1Dist = dijkstra(g);
        int[] inter2Dist = dijkstra(h);

        ArrayList<Integer> answer = new ArrayList<>();

        for(int idx = 0; idx < t; idx++) {
            int destination = destinations[idx];

            int dist1 = startDist[g] + pastEdgeWeight + inter2Dist[destination];
            int dist2 = startDist[h] + pastEdgeWeight + inter1Dist[destination];
            int shortest = Math.min(dist1, dist2);

            if(startDist[destination] == shortest)
                answer.add(destination);
        }

        Collections.sort(answer);

        for(int destination : answer)
            sb.append(destination).append(' ');
        sb.append('\n');
    }

    static int[] dijkstra(int start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        queue.offer(new Edge(start, 0));
        dist[start] = 0;

        while(!queue.isEmpty()) {
            Edge cur = queue.poll();

            if(dist[cur.cityNum] < cur.weight)
                continue;

            for(Edge e : map.get(cur.cityNum)) {
                int weight = e.weight + dist[cur.cityNum];

                if(dist[e.cityNum] > weight) {
                    dist[e.cityNum] = weight;
                    queue.offer(new Edge(e.cityNum, dist[e.cityNum]));
                }
            }
        }

        return dist;
    }

    static class Edge implements Comparable<Edge> {
        int cityNum, weight;

        public Edge(int cityNum, int weight) {
            this.cityNum = cityNum;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge e) {
            return this.weight - e.weight;
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

변수 선언 및 초기화

• 각 도로를 표현할 Edge 클래스를 생성합니다.
  • 이 클래스는 도착 도시를 나타내는 cityNum, 도로의 길이를 나타내는 weight를 멤버로 갖습니다.
  • 이후에 다익스트라 알고리즘을 사용할 것인데, 여기서 PriorityQueue에 Edge들을 넣어 진행할 예정인데 이 때 weight를 기준으로 오름차순으로 정렬할 수 있도록 Comparable을 구현하여 compareTo 메서드를 작성해줍니다.
• 교차로 개수를 나타내는 변수 n, 도로 개수를 나타내는 변수 m, 목적지 후보 개수를 나타내는 변수 t, 출발지를 나타내는 변수 s, 예술가들이 지난 교차로 사이 도로의 교차로를 나타내는 변수 g, h를 생성하고 입력을 받습니다.
• 목적지 후보들을 저장해놓을 배열 destination을 생성하고 각 도시에서 출발하거나 각 도시로 들어오는 도로들을 저장하기 위해 HashMap map을 생성합니다.
• 입력으로 들어오는 도로들을 HashMap에 저장하는데, 만약 해당 도로의 두 점이 g, h라면 pastEdgeWeight라는 변수에 해당 도로의 길이를 저장합니다. 이는 이후에 최소 거리를 계산할 때 사용할 예정입니다.
• 목적지 후보들을 입력받아 destination 배열에 저장합니다.

풀이

• 다익스트라 알고리즘을 이용하여 한 점에서 다른 모든 점으로의 최단 거리를 구합니다.
• 이 때, 시작점 s에 대해서 다익스트라 알고리즘을 돌려 최단 거리들을 startDist 배열에 저장하고 지나간 교차로의 두 점 g, h에 대해서 다익스트라 알고리즘을 돌려 최단 거리들을 각각 inter1Dist 배열과 inter2Dist 배열에 저장합니다.
• 가능한 목적지들을 담을 ArrayList answer를 생성합니다.
• 목적지 후보들 각각에 대해 시작점 s부터 시작하여 g, h 교차로를 지나 목적지로 가는 거리를 계산합니다.
  • startDist[g] 값(시작점 s에서 g로 가는 최단 거리)과 pastEdgeWeight(g, h 사이 교차로의 길이) 값을 더하고 inter2Dist[목적지](h에서 목적지로 가는 최단 거리) 값을 더해 시작점에서 g, h를 거쳐 목적지로 가는 거리를 계산합니다.
  • startDist[h] 값(시작점 s에서 h로 가는 최단 거리)과 pastEdgeWeight(h, g 사이 교차로의 길이) 값을 더하고 inter1Dist[목적지](g에서 목적지로 가는 최단 거리) 값을 더해 시작점에서 h, g를 거쳐 목적지로 가는 거리를 계산합니다.
  • 두 거리 중 더 짧은 거리를 찾아 shortest라는 변수에 저장합니다.
  • 만약 startDist[목적지] 값이 shortest와 같다면, 즉 시작점 s에서 목적지로 가는 최단 거리가 shortest 값과 같다면 해당 목적지로 갔을 가능성이 있으므로 해당 목적지를 answer에 저장합니다.
• answer를 오름차순으로 정렬하고 이를 출력합니다.