[백준] 9370번 : 미확인 도착지

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

# 출력

테스트 케이스마다

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

---

[Dijkstra 알고리즘]

개인적으로 난이도는 어렵지 않으나 코드가 길어지는 문제라고 생각된다. 문제를 이해하는 것이 조금 난해했다고 해야하나... 한 4번 째 읽는 것에서 완벽히 이해했다. 각 테스트 케이스에서 정점의 개수(n), 간선의 개수(m), 목적지 후보의 개수(t)가 주어진다.

 

그 다음 줄에서 s, g, h가 주어지는데 s는 시작 정점, g, h는 반드시 지나가야하는 간선이라고 생각하면 된다. 문제 풀이 시 주의할 점은, 시작 정점 s에서 g와 h 중 더 가까운(최단 경로가 더 작은 값) 곳을 구해야 한다. 문제 풀이의 핵심은 

 

1) 시작 정점에서 목적지 후보 정점까지의 최단 경로

2) 시작 정점 -> g -> g와 h사이의 가중치 -> h 에서 목적지 후보 정점 까지의 최단 경로 (시작 정점에서 g까지의 거리가 더 짧을 때로 가정)

 

를 비교해 같으면 답으로 출력해야하고, 다르면 출력해선 안된다.

 

1) 을 구하는 것은 일반적인 다익스트라 알고리즘으로 금방 구할 수 있으니 distance[0][]에 구해놨다고 치고,

 

2) 를 구하기 위해 distance[0][g]와 distance[0][h]를 비교해 더 적은 쪽을 택한다. 이 값을 기억해놓자.

h정점과 g정점 사이 간선의 가중치(bridge)는 인접 리스트를 돌며 구해놓을 수 있다.

            int bridge = -1;
            for (Edge e:list[g]) //인접 리스트 recursion
                if(e.tg == h) bridge = e.d; //g와 h 사이 간선의 가중치 get

이제 distance[1][]에 h 에서의 최단 경로를 구한다. 그럼 준비물은 모두 챙긴 것이다. 이제 1)과 2)를 비교해주기만 하면 된다. (min에 더 작은 값 g가 저장되어 있다.)

            Arrays.sort(arrive); //오름차순 정렬 하는 것이 좋다.
            
            for(int idx:arrive)
                if(distance[0][idx] == (distance[0][min] + bridge + distance[1][idx]))
                    System.out.print(idx + " ");
            System.out.println();

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int tg, d;
        public Edge(int target, int dist){
            tg = target; d = dist;
        }
        @Override
        public int compareTo(Edge o) {
            return d-o.d;
        }
    }

    static List<Edge>[] list;
    static Queue<Edge> Q = new PriorityQueue<>();
    static final int INF = 1000000000;
    static int[] distance[], arrive;
    static int v, e;

    static void Dijkstra(int start, int idx) {
        
        distance[idx][start] = 0;
        Q.add(new Edge(start, 0));

        while(!Q.isEmpty()){
            Edge edge = Q.poll();
            int current = edge.tg;
            int d = edge.d;

            if(distance[idx][current] < d) continue;

            for(Edge e : list[current]){
                int next = e.tg;
                int nextD = d + e.d;

                if(distance[idx][next] > nextD){
                    distance[idx][next] = nextD;
                    Q.add(new Edge(next, nextD));
                }
            }
        }
    }

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

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

        for(int a=0; a<t; a++) {

            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            int arrival = Integer.parseInt(st.nextToken());

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

            distance = new int[2][v+1];
            arrive = new int[arrival];
            list = new ArrayList[v+1];
            for(int i=1; i<=v;i++)
                list[i] = new ArrayList<>();

            for(int i=0; i<2; i++)
                for(int j=1; j<=v; j++)
                    distance[i][j] = INF;

            for(int i=0; i<e; i++){
                st = new StringTokenizer(br.readLine());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                list[b].add(new Edge(c, d));
                list[c].add(new Edge(b, d));
            }

            for(int i=0; i<arrival; i++)
                arrive[i] = Integer.parseInt(br.readLine());

            int min = INF;
            int bridge = -1;
            for (Edge e:list[g])
                if(e.tg == h) bridge = e.d;

            Dijkstra(start, 0);

            if(distance[0][g] < distance[0][h]){
                min = g;
                Dijkstra(h, 1);
            }

            else{
                min = h;
                Dijkstra(g, 1);
            }

            Arrays.sort(arrive);
            for(int idx:arrive)
                if(distance[0][idx] == (distance[0][min] + bridge + distance[1][idx]))
                    System.out.print(idx + " ");
            System.out.println();

            /*System.out.println("# 시작 정점에서의 최단 거리");
            Arrays.stream(distance[0]).skip(1).forEach(i->System.out.print(i + " "));
            System.out.println();
            System.out.println("# 중간 정점에서의 최단 거리");
            Arrays.stream(distance[1]).skip(1).forEach(i->System.out.print(i + " "));
            System.out.println();
            System.out.println("# Bridge: " + bridge);*/
        }
    }
}