[백준 / BOJ] 10021 Watering the Fields (Java)

문제

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

10021번: Watering the Fields

농부 존은 자신의 지역에 물을보내주는 시스템을 만들려고한다. 이때, 각 지역을 연결하는 비용은 다음과 같다.

 

연결비용 = (xi - xj)^2 + (yi - yj)^2

 

농부 존을 도와 물을 보내주는 시스템을 만드는 사람은 각 지역의 연결비용이 적어도 C이상일때만 각 지역을 연결한다.

 

농부 존이 연결해야할 지역의 수 N, 

최소 연결비용 C가 주어졌을때, 모든지역을 연결하는 최소비용을 구하는 문제다.

---

풀이

전형적인 MST문제다.

크루스칼로 풀었는데, PriorityQueue에 저장할때 두 지역의 거리가 C미만이라면, 저장하지않으면된다.

 

+ 구현에 따라 다르겠지만, 내 코드는 위 로직을 그대로 구현했는데 처음에 시간초과를 맞았다.

(클래스를 너무 많이 만들어서 그랬던듯)

C++로 구현한다면 아래부터 읽을 필요없다 그냥 MST쓰면 풀림

 

pq.가 빌때까지 반복하지않고, 따로 현재까지 연결된 지역의 수를 저장하는 변수를 만들어서 해당 변수가 N이되면 바로 break를 걸어줬다.

다음은 순서대로 (크루스칼 로직을 구현한) 고치기전, 고친후 코드다

private long solve(){
        long ret = 0;
        while(!pq.isEmpty()){
            int nowDistance = pq.peek().distance;
            int idx1 = pq.peek().idx1;
            int idx2 = pq.peek().idx2;
            pq.poll();
            if(checkUnionFind(idx1, idx2)) continue;
            mergeUnion(idx1, idx2);
            ret += nowDistance;
        }
        return ret;
    }

private long solve(){
        long ret = 0;
        int connect = 0;
        boolean[] check = new boolean[N+5];
        while(!pq.isEmpty()){
            int nowDistance = pq.peek().distance;
            int idx1 = pq.peek().idx1;
            int idx2 = pq.peek().idx2;
            pq.poll();
            if(connect == N) break;
            if(checkUnionFind(idx1, idx2)) continue;
            mergeUnion(idx1, idx2);
            if(!check[idx1]){
                check[idx1] = true; 
                connect++;
            }
            if(!check[idx2]){
                check[idx2] = true;
                connect++;
            }
            ret += nowDistance;
        }
        if(connect < N) return -1;
        return ret;
    }

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10021%20Watering%20the%20Fields/Main.java

devxb/JJUNalgo