[JAVA] 1647. 도시 분할 계획

도시를 분할 때 2개의 도시를 만들고 연결하는 최소의 유지비용을 구하는 문제이다.

최소의 거리값을 구하는 크루스칼 알고리즘을 사용하였다.

 

우선 최소의 비용을 구하기 위해 가장 작은 비용으로 모든 집을 연결해야했고, 그 중 최소의 연결 비용을 위해 가장 큰 값의 연결 유지비용을 제외해 마을을 나누어야 한다.

문제에서 2개의 도시는 최소 1개 이상의 집이 존재하여야 한다고 하였으므로 각 마을의 집을 모두 최소의 비용으로 연결한 후 마지막 가장 큰 비용으로 연결되어지는 하나의 집을 제외하여 다른 마을로 만들면 그 방식이 가장 최소의 비용으로 모든 집을 연결하고, 가장 큰 비용이 드는 집의 연결을 제거해 하나의 마을로 만드는 것이 최소의 유지비용이 될 것이다.

 

 

package algo;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class B_1647_도시분할계획 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Node[] list = new Node[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            int A = Integer.parseInt(st.nextToken()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;
            int C = Integer.parseInt(st.nextToken());
            list[i] = new Node(A, B, C);
        }
        int[] parents = new int[N];
        make(N, parents);
        Arrays.sort(list);
        int cnt = 0;
        int result = 0;
        for (int i = 0; i < M; i++) {
            if (union(list[i].start, list[i].end, parents)) {
                if (++cnt == N - 1)
                    break;
                result += list[i].weight; // 맨 마지막 연결을 제외하기 위해 if문 다음에 위치
            }
        }
        System.out.println(result);
    }
 
    private static void make(int N, int[] parents) {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }
 
    private static int find(int a, int[] parents) {
        if (a == parents[a])
            return a;
        return parents[a] = find(parents[a], parents);
    }
 
    private static boolean union(int a, int b, int[] parents) {
        int aRoot = find(a, parents);
        int bRoot = find(b, parents);
        if (aRoot == bRoot)
            return false;
        parents[aRoot] = bRoot;
        return true;
    }
 
    static class Node implements Comparable<Node> {
        int start, end, weight;
 
        public Node(int start, int end, int weight) {
            super();
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
}