[백준] 9370번 - 미확인 도착지 (Java)

문제

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

9370번: 미확인 도착지

 

입력

 

출력

---

알고리즘

다익스트라

 

문제를 요약하자면 시작지점 s로 부터 t개의 목적지 후보까지 g-h 간선을 포함해서 갈 수 있는 목적지 후보만 출력하는 것이다. 두가지 방법으로 풀어볼 것이다.

 

[ 방법 1 ]

 

우리가 체크해야 할 것은 s → 목적지 후보까지 가는 최단 경로에 g → h 또는 h → g가 포함되어 있는가이다. 따라서 모든 목적지 후보에 대해서 s →목적지까지 바로 가는 최단경로와  s → g → h → 목적지, s → h → g → 목적지 둘 중 하나의 최단 경로랑 같은지 확인하면 된다. 만약 최단 경로가 다르다면 g-h 간선을 포함하지 않는 것이 최단 경로라는 의미가 된다.

 

따라서 위와 같이 두 경우에 대해서 각각 다익스트라를 돌려주고, 그게 s → 목적지의 최단 경로랑 동일할 경우 답에 추가해주면 끝난다. 하지만 이 방법은 굉장히 많은 다익스트라를 돌려야 되다보니 효율성면에서 좋지 않다. 물론, 이렇게 풀려도 정답이 나오긴한다.

 

[ 방법 2 ]

 

위 방법은 다익스트라를 너무 여러번 돌린다. 딱 한번만 돌리고 답을 낼 수 있는 방법은 없을까? 이는 짝수와 홀수의 성질을 이용하면 된다. 짝수 + 짝수 = 짝수, 짝수 + 홀수 = 홀수 이다. 따라서, g-h 경로를 제외한 모든 경로를 짝수로 만들고 g-h 경로만 홀수로 만들고, dist배열에 기록된 최단 경로를 탐색했을때 그 값이 짝수인지 홀수인지만 확인하면 될 것이다. 만약에 g-h 간선을 거쳐서 최단경로를 만들었다면 최종 최단 경로는 홀수로 기록될 것이다.

 

따라서, g-h일 경우만 제외하고 모든 간선의 길이를 짝수로 만들어주기 위해서 2를 곱해준다. g-h의 경우에는 2*d - 1을 간선의 길이로 해주면 된다. 그런데 이때, 2*d + 1을 하면 안된다. 우리는 최단 경로를 구하는 것이기 때문에 + 1을 해서 값을 더 크게 해버리면 g-h를 거치는게 최단 경로가 아니라고 생각해서 무시하고 답을 내버릴 것이다. 따라서 2*d - 1로 설정해준다.

 

또한, 방법1의 경우 그냥 최종적으로 최단 경로가 같은지 아닌지를 비교하다보니깐 dist 배열을 최댓값으로 초기화할때 무지성 Integer.MAX_VALUE를 때려도 답이 나왔지만... 방법2로 할때는 명확하게 최댓값을 규명해주지 않으면

dist[node.end] > dist[end] + node.weight

이 부분에서 오버플로우가 나버린다. 이것때문에 진짜 계속 맞왜틀?을 외쳐가며 이유를 찾아갔다. 따라서, 최댓값으로 초기 값을 갱신할때 무지석 MAX값을 때리지 않도록 주의하자.

 

어쨌든, 최종 경로의 최댓값은 간선이 5만개이고 각 간선의 최대 길이가 1000이므로 5만*1000을 최댓값으로 설정해주면 된다. 

---

코드

[ 방법 1 ]

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

public class Main {
    public 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 this.weight - o.weight;
        }
    }

    static ArrayList<Node>[] nodelist;
    static int[] destination;
    static int n;

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

        int test = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(test-->0){
            StringTokenizer 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());

            nodelist = new ArrayList[n+1];
            for(int i = 1; i<n+1; i++){
                nodelist[i] = new ArrayList<>();
            }

            for(int i = 0; i<m; i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                nodelist[a].add(new Node(b, d));
                nodelist[b].add(new Node(a, d));
            }

            destination = new int[t];
            for(int i = 0; i<t; i++){
                destination[i] = Integer.parseInt(br.readLine());
            }

            ArrayList<Integer> answer = new ArrayList<>();
            //모든 목적지 후보에 대한 검사
            for(int next : destination){
                //s -> h, h -> g, g -> next 경로로 갔을때 최단 경로
                int case1 = dijkstra(s,h) + dijkstra(h, g) + dijkstra(g, next);
                //s -> g, g -> h, h -> next 경로로 갔을때 최단 경로
                int case2 = dijkstra(s,g) + dijkstra(g, h) + dijkstra(h, next);
                //s -> next로 갔을때 최단 경로
                int base = dijkstra(s, next);
                //g -> h 또는 h -> g 경로가 있을때만 최종 목적지임
                if(Math.min(case1, case2) == base) answer.add(next);
            }
            
            //최종 목적지 출력
            Collections.sort(answer);
            for(int a : answer){
                sb.append(a + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
    
    //그냥 다익스트라 알고리즘
    public static int dijkstra(int s, int e){
        boolean[] check = new boolean[n+1];
        int[] dist = new int[n+1];
        Arrays.fill(dist, 50000*1000);

        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(s, 0));
        dist[s] = 0;

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            int end = cur.end;

            if(check[end] == true) continue;
            check[end] = true;

            for(Node node : nodelist[end]){
                if(!check[node.end] && dist[node.end] > dist[end] + node.weight){
                    dist[node.end] = dist[end] + node.weight;
                    queue.add(new Node(node.end, dist[node.end]));
                }
            }
        }

        return dist[e];
    }
}

 

[ 방법 2 ]

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

public class Main {
    public 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 this.weight - o.weight;
        }
    }

    static ArrayList<Node>[] nodelist;
    static int[] dist;
    static int n;

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

        int test = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(test-->0){
            StringTokenizer 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());

            nodelist = new ArrayList[n+1];
            for(int i = 1; i<n+1; i++){
                nodelist[i] = new ArrayList<>();
            }

            for(int i = 0; i<m; i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                //g-h 간선에 대해서만 홀수로 설정
                if((a == g && b == h) || (a== h && b == g)) d = d*2 - 1;
                //나머지 간선은 전부다 짝수로 설정
                else d *= 2;
                nodelist[a].add(new Node(b, d));
                nodelist[b].add(new Node(a, d));
            }

            dist = new int[n+1];
            //간선의 개수는 5만개, 간선의 최대 길이는 1000이므로 5만*1000을 최댓값으로 설정
            //그냥 Integer.MAX_VALUE로 하면 dist[node.end] > dist[end] + node.weight 이 과정에서 오버플로우나서 틀립니다.
            Arrays.fill(dist, 50000*1000);

            ArrayList<Integer> destination = new ArrayList<>();
            for (int i = 0; i < t; i++){
                destination.add(Integer.parseInt(br.readLine()));
            }

            dijkstra(s);

            Collections.sort(destination);

            //만약 최종 간선의 최단 경로가 홀수다? 그럼 g-h경로를 포함한 것임 따라서 답
            for (int num : destination) {
                if (dist[num] % 2 == 1) sb.append(num + " ");
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }

    //그냥 다익스트라 알고리즘
    public static void dijkstra(int s){
        boolean[] check = new boolean[n+1];

        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(s, 0));
        dist[s] = 0;

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            int end = cur.end;

            if(check[end] == true) continue;
            check[end] = true;

            for(Node node : nodelist[end]){
                if(!check[node.end] && dist[node.end] > dist[end] + node.weight){
                    dist[node.end] = dist[end] + node.weight;
                    queue.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }
}