[JAVA] 백준 1800 - 인터넷 설치

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

K개의 무료 연결을 제외한 나머지 (경로 - K)개의 케이블선의 가중치의 MAX값의 최솟값을 구하는 문제이다.

첫번째로 일반적인 다익스트라로 JAVA의 comparable 인터페이스를 구현해 정렬기준을 수정해서 풀어보려고 시도했지만 예외케이스가 너무 많았다.

    @Override
    public int compareTo(N1800 o) {
        Collections.sort(this.costList);
        Collections.sort(o.costList);

        if (this.costList.size() < freeCount + 1 && o.costList.size() < freeCount + 1) { //둘다 FreeCount 이내일 경우 Cost 비교
            if(this.value==this.lastValue)return -1;
            return Double.compare(this.cost, o.cost);
        } else if (this.costList.size() >= freeCount + 1 && o.costList.size() < freeCount + 1) { //this는 FreeCount 초과했을 경우
            int tmax = this.costList.get(this.costList.size() - 1 - freeCount);
            int omax = (int) o.cost;
            return tmax - omax;
        } else if (this.costList.size() < freeCount + 1 && o.costList.size() >= freeCount + 1) {//o는 FreeCount 초과했을 경우
            int tmax = (int) this.cost;
            int omax = o.costList.get(o.costList.size() - 1 - freeCount);
            return tmax - omax;
        } else { //둘다 freecount를 초과했다 ->
            int tmax = this.costList.get(this.costList.size() - 1 - freeCount);
            int omax = o.costList.get(o.costList.size() - 1 - freeCount);
            //System.out.println(this.value + " VS " + o.value + " " + this.costList.size() + " " + o.costList.size() + " " + tmax + " " + omax);
            return tmax - omax;
        }
    }
}

이런 식으로 어거지로 풀어보려고 했지만 모든 상황에서 반례가 존재했다.

 

2번째로는 목적지 정점에서 K번째 이동까지 BFS를 돌려 각 정점에 (목적지 -> 해당 정점) 의 가중치 리스트를 저장하고, 1번에서 다익스트라를 이용해 아까 K번 이하로 이동한 정점에 대해 BFS 가중치 list count + 다익스트라 가중치 list count - 무료 연결 count의 max값을 구하려고 했는데 이것도 반례가 너무 많았다.

 

질문 게시판에 어떤 분이 "X일 때 안되는데 X-1일 때 될까요?"라는 힌트를 올려놓은걸 보고 가격을 미리 정해두고 탐색을 해야겠다는 생각을 했지만 범위가 1부터 100만이라 전체 탐색은 무리가 있을 것 같았다.

 

결국 GPT한테 범위 탐색을 효율적으로 할 수 있는 방법을 물어봤고 이분탐색이라고 답변받았다.

너무 안써서 잊고있었다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int target = info[0];
        int vertexCount = info[1];
        int freeCount = info[2];
        List<N1800> nodeList = new ArrayList<>();
        for (int i = 0; i <= target; i++) {
            nodeList.add(new N1800(i));
        }
        nodeList.get(target).cost = 0;
        for (int i = 0; i < vertexCount; i++) {
            int[] vertex = getArray(br.readLine());
            nodeList.get(vertex[0]).add(new V1800(vertex[1], vertex[2]));
            nodeList.get(vertex[1]).add(new V1800(vertex[0], vertex[2]));
        }
        PriorityQueue<N1800> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[nodeList.size()];
        int left = 0;
        int right = 1000000;
        int answer = -1;
        while(left<=right){
            visited = new boolean[nodeList.size()];
            int mid = (left+right)/2;
            for (int i = 2; i <=target ; i++) {
                nodeList.get(i).cost = Double.MAX_VALUE / 1000;
            }
            N1800 start = copyObject(nodeList.get(1));
            start.cost = 0;
            pq.clear();
            pq.offer(start);
            while (!pq.isEmpty()) {
                N1800 t = pq.poll();
                int value = t.value;
                double cost = t.cost;
                if(visited[value]) continue;
                visited[value] = true;
                if(value==target){
                    nodeList.get(target).cost = cost;
                    break;
                }
                List<V1800> vList = t.vertexList;
                for (V1800 v : vList) {
                    int costs = -1;
                    if (v.cost > mid) costs = 1;
                    else costs = 0;
                    N1800 tn = copyObject(nodeList.get(v.to));
                    if (tn.cost > costs + cost) {
                        tn.cost = costs + cost;
                        pq.offer(tn);
                    }
                }
            }

            if(nodeList.get(target).cost==Double.MAX_VALUE / 1000){ //도달 불가
                System.out.println(-1);
                return;
            }
            if(nodeList.get(target).cost>freeCount){ //실패 -> mid이상의 케이블을 freecount번 이상 사용했음
                left = mid+1;
            }else{
                right = mid -1;
                answer = mid;
            }
        }

        System.out.println(answer);
    }

    static N1800 copyObject(N1800 t) {
        N1800 target = new N1800(t.value);
        target.vertexList.addAll(t.vertexList);
        return target;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class N1800 implements Comparable<N1800> {
    int value;
    double cost = Double.MAX_VALUE / 1000;
    List<V1800> vertexList = new ArrayList<>();

    N1800(int value) {
        this.value = value;
    }

    void add(V1800 v) {
        this.vertexList.add(v);
    }

    @Override
    public int compareTo(N1800 o) {
        return Double.compare(this.cost,o.cost);
    }
}

class V1800 {
    int to;
    int cost;

    V1800(int t, int c) {
        this.to = t;
        this.cost = c;
    }
}

 

0부터 100만까지의 범위에서 이분탐색을 진행하고, mid값보다 가중치가 클 경우 1, 작을 경우 0으로 가중치를 변형한 후 

가중치가 free count번 이상이면 실패(정답은 현재 mid보다 큼), 이하면 성공(정답은 현재 mid보다 작음)으로 처리하고 범위를 줄여나갔다.