[백준 9370 : JAVA] 미확인 도착지 / 다익스트라

개요

 

다익스트라를 이용해서 풀이할 수 있는 문제이다.

다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다.

아래에 링크에는 다익스트라 알고리즘에 대한 설명이 포함되어 있다.

2020/02/09 - [알고리즘/백준] - [백준 1753 : JAVA] 최단경로 / 다익스트라

[백준 1753 : JAVA] 최단경로 / 다익스트라

이 문제는 말은 길지만 간단히 정리하면 

출발점 -> 도착지 까지의 최단거리 중 특정 간선을 지나는 경우를 구하는 문제이다.

예를 들어 1 -> 5 정점까지의 최단거리가  2->3간선을 지나는지? 여부를 확인하면 되는 문제이다.

 

문제

 

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는 지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

 

입력

 

풀이

 

첫번쨰 테스트를 그래프화 해보면 아래와 같다.

아래에서 초록색은 시작점이고 주황색은 우리가 확인해야하는 간선이다.

위와 같은 그래프가 있을 때 2가지 풀이법이 있다.

 

문제의 입력처럼 1에서 5까지 가는데 최단 경로에 2-3이 포함되는가?를 묻는다면

 

1.

(1 -> 2 최단거리) + (2 -> 3 최단거리) + (3 -> 5 최단거리) == (1 -> 5 최단거리) 

또는 (1 -> 3 최단거리) + (3 -> 2 최단거리) + (2 -> 5 최단거리) == (1 -> 5 최단거리) 

를 만족한다면 포함이 된다는 뜻으로 해석할 수 있다.

 

하지만 이 풀이는 다익스트라를 여러번 호출하기 때문에 효율적이지는 않지만 간단히 생각해낼수 있는 방법이다.

 

2. 

가중치를 저장할 떄 아래의 그림과 같이 주황색 간선은 2를 곱하고 -1을 해주어 홀수를 만들고

나머지 간선은 2를 곱해서 짝수를 만들어준다.

위와 같이 가중치를 저장하고 1 -> 5의 최단거리를 다익스트라를 통해 구한다면

만약 최단거리가 홀수라면 주황색 간선을 지나고 온다는 뜻이 되고, 최단거리가 짝수라면 주황색 간선을 지나지 않는다는 뜻이된다.

왜냐하면, '(짝수 + 짝수 ... + 짝수) + 홀수 = 홀수' 이고 '(짝수 + 짝수 ... + 짝수) = 짝수' 이기 때문이다.

또한 이처럼 풀이하게 되면 최단거리가 같은 경우도 따로 생각하지 않고 구할 수 있다.

 

코드

 

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

public class Main {
    static class Node implements Comparable<Node>{
        int end, weight;

        public Node(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 10_000_000;
    static int vertex, edge, t;
    static int start, g, h;
    static int arr[][];
    static int dist[];
    static boolean check[];
    static List<Integer> answerList;


    public static void main(String[] args) throws IOException {
        int testCnt = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < testCnt; i++){
            // n,m,t 초기화
            StringTokenizer st = new StringTokenizer(br.readLine());
            vertex = Integer.parseInt(st.nextToken());
            edge = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());

            // 그래프 배열 선언
            arr = new int[vertex + 1][vertex + 1];
            dist = new int[vertex + 1];
            for(int j = 0 ; j < arr.length; j++)
                Arrays.fill(arr[j], INF);
            Arrays.fill(dist, INF);
            check = new boolean[vertex + 1];

            // s, g, h 초기화
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            // 그래프 정보 저장
            for(int j = 0 ; j < edge; j++){
                st = new StringTokenizer(br.readLine());
                int vertex1 = Integer.parseInt(st.nextToken());
                int vertex2 = Integer.parseInt(st.nextToken());
                int distance = Integer.parseInt(st.nextToken());
                // 2배의 가중치를 저장
                arr[vertex1][vertex2] = arr[vertex2][vertex1] = distance * 2;
            }
            // 2배된 값에 -1을 하여 홀수를 만든다.
            arr[h][g] = arr[g][h] = arr[h][g] - 1;

            // 후보정답 list선언
            answerList = new ArrayList<>();
            // 후보가 되는 값 추가
            for(int j = 0; j < t; j++)
                answerList.add(Integer.parseInt(br.readLine()));

            solve();
            // 오름차순 정렬
            Collections.sort(answerList);
            // 정답 출력
            for(int num : answerList)
                if(dist[num] % 2 == 1) bw.write(num + " ");
            bw.write("\n");
        }

        bw.close();
        br.close();
    }

    private static void solve() {
        dijkstra();
    }

    private static void dijkstra(){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));
        dist[start] = 0;

        // 큐가 빌 때까지
        while(!queue.isEmpty()){
            Node curNode = queue.poll();
            int cur = curNode.end;
            // 이미 방문한 노드인 경우 패스
            if(check[cur]) continue;
            // 방문 처리
            check[cur] = true;

            for(int i = 1; i <= vertex; i++){
                if(check[i] == false && dist[i] > dist[cur] + arr[cur][i]){
                    dist[i] = dist[cur] + arr[cur][i];
                    queue.add(new Node(i, dist[i]));
                }
            }
        }
    }
}