[JAVA] 백준 10217 KCM Travel

오늘의 문제 : https://www.acmicpc.net/problem/10217

 

안뇽하세요. 오늘은 김찬민 씨를 위해 LA로 가는 비행기 편을 알아봐야 합니다. 알아봐 주면 혹시 짐꾼으로 데려가주지 않을래? 

 

정답률이 10%인 문제라서 긴장하고 풀었습니다. 

 

1번에 N번 노드까지의 사용가능한 비용 안에서 최소 도달 시간을 구해야합니다. 비용도 양수이고 출발점과 도착점이 정해져 있어서 다이젝스트라 알고리즘을 사용하면 됩니다.

 

근데 문제가 있습니다.

 

다이젝스트라 알고리즘이 야무진 이유가 "첫 방문이 최단거리" 라는 기가 막힌 조건이라고 생각합니다. 하지만 현재 문제에서는 그 조건이 성립하지 않습니다. 

 

위 그래프에서 3번까지의 최단 시간은 2이지만, 만일 사용가능한 비용이 5라면 4가 됩니다. 즉 1번에서 2번으로 가는 간선 2개 중 시간은 더 걸리지만 비용은 작은 간선이 정답이 될 수 도 있습니다. 즉 현재 비용에서 갈 수 있는 모든 간선을 확인해 줘야 합니다. 곤란하네요

 

그래서 제가 처음 생각한 방법은 기존 다익스트라의 

if(지금까지 비용 + 현재 간선 비용 < 목적지 비용) 조건을 조금 더 느슨하게 해 줬습니다. 

 while(!pq.isEmpty()){
            Pair now = pq.poll();
            for(Pair edge : edges[now.now]){
                if(now.cost + edge.cost < budget){
                    if(ans[edge.now] > now.time+edge.time){
                        ans[edge.now] = now.time+edge.time;
                    }
                    if(edges[edge.now] != null) pq.add(new Pair(edge.now, now.cost+edge.cost,edge.time+ now.time));
                }
            }
        }

if(지금까지 비용 + 현재 간선 비용 < 목적지 비용) true 이면  ans에 그 값을 저장해서 업데이트를 하고, false여도 총비용보다 작으면 그냥 pq에 넣어줬습니다.

 

시간 초과가 나왔습니다. 

예를 하나만 들어보자면 뭐 이렇게 같은 간선이 여러개가 있을 때면 pq에 굉장한 비효율을 야기합니다. 아쉽네요 다른 방법을 찾아야 합니다. (저는 여기서 '문제 알고리즘 분류보기' 권법을 사용했습니다.)

 

위와 같은 예시를 막기위해서 ans 배열 (각 지점까지 최단거리 )에 비용의 정보도 함께 저장해 주었습니다.

 ans [1][1] = 1로 저장했으니 다음 1,1은 큐에 넣지 않습니다. 

 for(Pair edge : edges[now.now]){
                if(now.cost + edge.cost <= budget){
                    if(ans[edge.now][now.cost + edge.cost] > now.time+edge.time){
                        ans[edge.now][now.cost + edge.cost] = now.time+edge.time;
                        if(edge.now == n) min = Math.min(min, now.time+edge.time);
                        if(edges[edge.now] != null) pq.add(new Pair(edge.now, now.cost+edge.cost,edge.time+ now.time));
                    }
                }
            }

 

하지만 또 시간초과가 나왔습니다. 뭔가 더 해줘야 합니다. 

 

비효율이 발생하는 케이스를 생각해 보면..

 

자 여기서 3,5 간선을 진행했다면  4,9 간선을 확인할 이유가 있을까요? 비용이 더 큰데 더 큰 시간을 가지는 간선은 절대 정답이 될 수 없습니다. 즉 이 경우 4,9는 확인할 필요가 없어집니다. 

 for(Pair edge : edges.get(now.now)){
                if(now.cost + edge.cost <= budget){
                    if(ans[edge.now][now.cost + edge.cost] > now.time+edge.time){
                        ans[edge.now][now.cost + edge.cost] = now.time+edge.time;
                        for(int i = now.cost+edge.cost+1; i<=budget;i++){
                            if(ans[edge.now][i] > now.time+edge.time){
                                ans[edge.now][i] = now.time+edge.time;
                            }else{
                                break;
                            }
                        }
                        if(edge.now == n) min = Math.min(min, now.time+edge.time);
                        pq.add(new Pair(edge.now, now.cost+edge.cost,edge.time+ now.time));
                    }
                }
            }

 

위 경우를 막기 위해서 만일 ans [2][3] = 5로 탐색이 가능하다면 ans [2][4,5,.... m]까지 다 5와 비교해 주는 로직을 추가했습니다. 

 

이 로직을 통해 통과하긴 했지만 좀 더 이야기할 만한 주제가 있습니다. 정답 코드 먼저 올라고 말할까요?

-코드

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

public class Main {
    private static class Pair {
        int now;
        int cost;
        int time;
        Pair(int now, int cost , int time){
            this.now = now;
            this.cost = cost;
            this.time = time;
        }
    }
    static int n,budget, edge;
    static List<List<Pair>> edges;
    static int[][] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        budget = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        edges = new LinkedList<>();
        for(int i=0;i<=n;i++){
            edges.add(new LinkedList<>());
        }
        for(int i=0;i<edge;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edges.get(start).add(new Pair(end,cost,time));
        }
        ans = new int[n+1][10001];
        for(int i=1;i<=n;i++){
            Arrays.fill(ans[i],Integer.MAX_VALUE);
            edges.get(i).sort(new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.time - o2.time;
                }
            });
        }
        ans[1][0] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if(o1.time == o2.time) return o1.cost - o2.cost;
                return o1.time - o2.time;
            }
        });
//        Deque<Pair> pq = new LinkedList<>();
        pq.add(new Pair(1,0,0));
        int min = Integer.MAX_VALUE;
        Loop1:
        while(!pq.isEmpty()){
            Pair now = pq.poll();
            if(ans[now.now][now.cost] < now.time) continue;
            for(Pair edge : edges.get(now.now)){
                if(now.cost + edge.cost <= budget){
                    if(ans[edge.now][now.cost + edge.cost] > now.time+edge.time){
                        ans[edge.now][now.cost + edge.cost] = now.time+edge.time;
                        for(int i = now.cost+edge.cost+1; i<=budget;i++){
                            if(ans[edge.now][i] > now.time+edge.time){
                                ans[edge.now][i] = now.time+edge.time;
                            }else{
                                break;
                            }
                        }
                        if(edge.now == n) min = Math.min(min, now.time+edge.time);
                        pq.add(new Pair(edge.now, now.cost+edge.cost,edge.time+ now.time));
                    }
                }
            }
        }
        if(min == Integer.MAX_VALUE){
            System.out.println("Poor KCM");
        }else{
            System.out.println(min);
        }
    }
}

 

이 문제의 질문 게시판을 보면 pq를 que로 바꿔주니 통과했다는 분들이 있었습니다. 

 

하지만 이 문제를 que를 사용하여 풀면 안 된다는 의견이 있어서 저도 생각해 봤습니다. https://www.acmicpc.net/board/view/129181

 

que 사용한다면 pq의 정렬하는 데 걸리는 시간 복잡도를 단축시킬 수 있습니다. que로 바꾸는 이유는 위 문제는 다익스트라 알고리즘에서 "최초 방문이 곧 최단거리"라는 조건이 이 문제 상황에서는 성립하지 않고 결국 다른 경우까지 다 확인을 해줘야 하기 때문이라고 생각합니다.

 

또한 edges의 정렬 조건을 pq 정렬 조건과 같게 해 준다면 그 과정도 같을 것 같아서 직접 테스트를 해봤습니다. 

 

입출력 값은 질문 게시판에서 재채점을 요청하신 두 분의 데이터를 입력했고 

input a

https://www.acmicpc.net/board/view/75576

Input file / Output file

 

input b

https://www.acmicpc.net/board/view/146379

kcm4.in kcm4.out

 

1. pq를 사용한 위 코드

input a : 1.3 ms

input b : 3.9 ms

 

2. deque을 사용한 코드

input a : 1.2 ms

inout b : 6.9 ms

 

input b에서 pq를 사용한 코드가 눈에 띄게 효율적인 것을 확인했습니다. 왜 그럴까요. 사실 아직 그 이유를 못 찾았습니다.