[백준 / BOJ] 1414 불우이웃돕기 Prim (Java)

문제

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

1414번: 불우이웃돕기

N개의 컴퓨터가 있고, 각 컴퓨터를 연결하는 랜선이 N*N개 주어진다. 

다솜이는 자신의 컴퓨터를 최소한의 랜선을 사용해서 연결하고 나머지 랜선을 기부할려고한다.

이때, 다솜이가 기부할수있는 최대 랜선 길이를 구하는 문제다.

---

풀이

MST문제다.

다솜이가 컴퓨터를 연결하는 과정에서, 연결 순서, 방법등 아무것도 고려하지않고 "최소한의 랜선길이"만 유지하면 되므로 MST로 풀리는 문제였다.

 

이 문제의 그래프는 양방향 간선이지만, A->B로 갈때의 가중치와 B->A로 갈때의 가중치가 다르다는 점때문에, 일반적인 프림으로 풀면 통과할수가없다.

(크루스칼로 구현하면 별도의 추가 구현없이 통과할거 같기는 하다 아마도..?)

 

위 빨간색 부분을 처리하는게 중요한 문제였다.

프림 알고리즘은, 현재 트리에 연결된 노드가 가진 간선중 최소 가중치 간선을 선택해서 연결해 나간다. 하지만, 이 조건이 항상 성립하려면, 노드 A->B로 가는 간선이 단방향 간선이거나 노드 A->B로 가는 간선과 B->A로 가는간선의 가중치값이 일치해야한다. 

 

예를들어, 노드 A->B를 연결하는 간선의 가중치가 3, 노드 B->A를 연결하는 간선의 가중치가 1 이라고 하자. MST는 어떤 방식으로 연결하던, 결과가 최소스패닝트리이기만 하면 상관이없다. 즉, 위와 같은 상황에서는 A->B가 아닌 B->A를 연결하는게 답이다.

 

하지만, 시작지점을 잡고 탐색을하는 프림알고리즘의 경우, 시작지점을 A로 잡았을때 별도의 구현없이는 (일반적인 프림은 A->B로 가는 간선과 B->A로 가는 간선이 똑같다고 가정하고 수행한다.) 항상 A->B로 가는 가중치간선을 선택한다.

시작지점을 A로 잡았을때 A->B 와 B->A를 전부 봐주기위해서 다음 조건을 추가했다.

다음 가중치값 = min(A->B,B->A);

A->B, B->A모두 A와 B를 연결한것이므로 이렇게 구현해도 항상 성립하는걸 알수있다.

 

프림 코드 

    private int setCables(int startIdx){
        int ret = 0, cnt = 0;
        boolean[] check = new boolean[N+5];
        PriorityQueue<Computer> pq = new PriorityQueue<Computer>();
        pq.add(new Computer(0,startIdx));
        while(!pq.isEmpty()){
            int nowComputer = pq.peek().computer;
            int nowCableLength = pq.peek().cableLength;
            pq.poll();
            if(check[nowComputer]) continue;
            check[nowComputer] = true;
            ret += nowCableLength;
            cnt++;
            for(int i = 0; i < N; i++){
                if(cable[nowComputer][i] == INF && cable[i][nowComputer] == INF) continue;
                pq.add(new Computer(Math.min(cable[nowComputer][i],cable[i][nowComputer]), i));
            }
        }
        if(cnt < N) return -1;
        return totalCableLength - ret;
    }

cable은 가중치값을 저장한 배열이다.

 

프림 알고리즘에 대한 이해가 중요한 문제였다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1414%20%EB%B6%88%EC%9A%B0%EC%9D%B4%EC%9B%83%EB%8F%95%EA%B8%B0/Main.java

devxb/JJUNalgo