[백준 / BOJ] 1800 인터넷 설치 (Java)

문제

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

1800번: 인터넷 설치

원장선생님이 세미나 실에 인터넷을 설치해주기로 마음을 먹었다.

 

목표는 N번 컴퓨터가 인터넷에 연결되는것이다. 나머지 컴퓨터는 연결이 안되어있어도 된다.

인터넷을 설치하는데 일정 비용이들며, P개의 인터넷 선이 있고, 이중 K개를 무료로 설치할수있을때, 인터넷을 설치하는 최소 비용을 구하는 문제다. (설치비용은 설치된 인터넷선중 가장 비싼 것에 대해서만 가격을 받는다.)

---

풀이

결정문제로 풀리는 문제다.

처음엔 MST인줄알고 한참을 고민했다... (K개를 무료로 하는 조건때문에 MST로는 풀기 어려워보인다.)

 

문제의 요구하는 조건을 다음과 같이 바꿔보자.

 

컴퓨터 N을 연결하는 최소비용을 구하라. -> 최대 cost의 돈으로 컴퓨터 N을 인터넷에 연결시킬수있는가?

이제 바뀐 요구조건에 대해서 답하는 코드를 만들면된다.

 

구현은 아래와 같다.

cost는 1원부터 1,000,000까지 갈수있다. 이를 이분탐색으로 구해준다.

    private int solve(){
        int ret = -1;
        int low = 1, max = 1000000;
        for(int i = 1; i <= 21; i++){
            int mid = (low + max) / 2;
            if(connect(mid)){
                ret = mid;
                max = mid - 1;
            }
            else low = mid + 1;
        }
        return ret;
    }

21번 반복하면, 매 반복마다 오차범위가 1/2씩 줄어드니, 오차범위를 1/2,000,000 만큼 줄일수있다. 따라서 항상 답을 구할수있다.

(평균시간은 low < max로 반복시켜주는거보다 더 오래걸리긴한다)

 

connect는 mid값으로 N까지 연결할수있는지 체크해주는 함수이다.

    private boolean connect(int maximumCost){
        int[] check = new int[N+5];
        fill(check);
        check[1] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>(); // K사용횟수, 현재 노드
        pq.add(new Pair(0,1));
        while(!pq.isEmpty()){
            int restK = pq.peek().first;
            int node = pq.peek().second;
            pq.poll();
            if(check[node] < restK || restK > K) continue;
            if(node == N) return true;
            for(int i = 0; i < edge.get(node).size(); i++){
                int nextNode = edge.get(node).get(i).second;
                int nextK = restK;
                if(edge.get(node).get(i).first > maximumCost) nextK++;
                if(check[nextNode] <= nextK) continue;
                check[nextNode] = nextK;
                pq.add(new Pair(nextK, nextNode));
            }
        }
        return false;
    }

pq에 {전깃줄을 무료로 연결할수있는 기회를 사용한 횟수, 현재노드}로 저장해준다.

탐색중 maximumCost보다 높은 가격을 요구하는 전깃줄을 만나면 전깃줄을 무료로 연결할수있는 기회를 사용한 횟수 를 1씩 증가시켜주면서 탐색하면된다.

N까지 연결할수있다면 true를 반환하고 아니면 false를 반환한다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1800%20%EC%9D%B8%ED%84%B0%EB%84%B7%20%EC%84%A4%EC%B9%98/Main.java

devxb/JJUNalgo