[BOJ 1647] 도시 분할 계획 - JAVA, Gold4

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

1647번: 도시 분할 계획

풀이

사용한 알고리즘 : 크루스칼 알고리즘

 

풀이전략

 

문제는 최소 신장트리를 만들 것을 요구하고 있다.

 

최소 신장트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

<출처> 이것이 코딩 테스트다 with Python (나동빈)

문제에서는 마을 내부의 모든 집이 연결되면서, 비용이 최소가 되도록 길을 연결했을 경우의 비용을 요구하고있기 때문에, 최소 신장트리를 만들고, 만든 트리 간선들의 비용 합을 구하면 된다.

 

단, 마을을 2개 구역으로 분리시키라고 했으므로 비용이 가장 많이 드는 간선을 하나 제거하여

남아있는 길들의 비용 합산이 최소이면서 구역이 2개로 분리되도록 한다.

 

크루스칼 알고리즘은 greedy 알고리즘의 일환이다.

입력받은 모든 간선들 중에서 비용이 가장 작은 값부터 시작하여 그래프를 생성하기 때문이다.

 

동작과정은 아래와 같다.

 

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인한다.

   -  사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.

   -  사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.

3. 모든 간선에 대해 2번 과정을 반복한다.

 

위 과정에서 사이클이 발생하는지 알아보는 방법은

연결하려는 두 집이 같은 부모 노드를 가지는 같은 집합인지 아닌지 확인하면 된다.

 

같은 부모를 가진다는 것, 즉 같은 집합에 있다는 것은 두 집이 이미 연결되어 있었다는 의미인데

static int find_parent(int x){
    if(x==parent[x]) return x;
    return find_parent(parent[x]);
}

static void union_node(int a,int b){
    int A = find_parent(a);
    int B = find_parent(b);
    if(A>B) parent[A]=B;
    else parent[B]=A;
}

위 코드에서와 같이 두 집을 연결할 때 부모의 값을 두 부모 중 더 작은 값으로 일치시키기 때문이다.

 

따라서 이전의 크루스칼 알고리즘 동작과정을 마친 뒤,

[생성된 그래프의 간선들의 비용 총합] - [그래프 내 간선들 중 가장 큰 비용] 을 구하면 된다.

 

이는 마을을 2 구역으로 나누면서 같은 구역 내 모든 집들이 길로 연결되고,

길 유지비의 합이 최소인 값이다.

 

<문제 풀이 시 주의해야할 점>

1. Collections 클래스의 sort 메소드를 통해 정렬할 때, 클래스 객체 내부의 Comparable 구현 메소드인 compareTo에서  Collections.sort를 사용한 경우 Comparator에 대해 모든 x, y가 sgn(compare(x, y)) == -sgn(compare(y, x))를 성립하지 않으면 IllegalArgument Exception 이 발생한다

 

아래와 같이 비교하는 값이 동일한 경우를 따로 설정해두지 않으면

@Override
public int compareTo(Node o) {
    if (this.cost < o.cost) return -1;
    else return 1;
}

IllegalArgument Exception이 발생한다.

 

따라서 아래와 같이 비교하는 값이 동일한 경우 0을 반환하도록 수정해야한다.

@Override
public int compareTo(Node o) {
    if (this.cost < o.cost) return -1;
    else if (this.cost > o.cost) return 1;
    else return 0;
}

 

2. 입력받은 집의 개수가 2개인 경우, 두 집 사이의 길이 필요 없으므로 0을 출력하도록 한다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static int parent[];
    static int find_parent(int x){
        if(x==parent[x]) return x;
        return find_parent(parent[x]);
    }

    static void union_node(int a,int b){
        int A = find_parent(a);
        int B = find_parent(b);
        if(A>B) parent[A]=B;
        else parent[B]=A;
    }

    static class Node implements Comparable<Node>{
        int cost;
        int houseA;
        int houseB;

        public Node(int cost,int houseA,int houseB){
            this.cost=cost;
            this.houseA=houseA;
            this.houseB=houseB;
        }

        @Override
        public int compareTo(Node o) {
            if(this.cost<o.cost) return -1;
            else if(this.cost>o.cost) return 1;
            else return 0;
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[N];

        for(int i=0;i<N;++i){
            parent[i]=i;
        }

        ArrayList<Node> list = new ArrayList<>();

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            Node node = new Node(C,A-1,B-1);
            list.add(node);
        }
        Collections.sort(list);

        int result=0;
        int count=0;
        for(Node node:list){
            if(N==2) break;
            if(find_parent(node.houseA)!=find_parent(node.houseB)){
                union_node(node.houseA,node.houseB);
                result+=node.cost;

                ++count;
                if(count==N-2) break;

            }
        }
        bw.write(result+"\n");
        bw.flush();
        bw.close();
    }
}