[BOJ/MST] 백준 1647 - 도시 분할 계획 (Java)

1647 - 도시 분할 계획

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

문제

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이뤄짐
길은 어느 방향으로든지 다닐 수 있고 길을 유지하는데 드는 유지비 있음

마을을 2개의 분리된 마을로 분할할 계획
-> 분할 시 각 분리된 마을 안에 집들이 서로 연결 = 각 분리된 마을 안에 있는 임의의 두 집 사이 경로 항상 존재
/ 마을에 집이 하나 이상 있어야 함, 분리된 마을 사이 있는 길 없앨 수 있음
=> 길 모두 없애고 나머지 길의 유지비 합 최소

입력
첫째 줄: 집의 개수 N (2 <= N <= 100,000), 길의 개수 M (1 <= M <= 1,000,000)
다음 줄 ~ M줄: 길의 정보 A B C (1 <= C <= 1,000) (A번 집과 B번 집을 연결하는 길의 유지비 C)
(임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어짐)
출력: 없애고 남은 길 유지비의 합의 최솟값

---

풀이

• Kruskal 알고리즘 (최소 신장 트리, MST)
  • 간선을 비용 기준 오름차순으로 정렬
  • Union-Find로 사이클 생기지 않게 연결
    • `union(e.a, e.b)`
  • 모든 정점 연결하면서 최소 비용 유지
• 가장 비싼 간선 하나 제공
  • MST 만들면 전체 연결됨
    • 비용 작은 간선부터 선택해서 전체 연결
  • 한 개의 간선 제거 -> 두 개의 마을로 분리
  • 최솟값 = 전체 비용 - 가장 큰 간선 비용
    • `total += e.cost`
    • `maxCost = e.cost`: 순서 정렬 -> 마지막 간선 비용이 가장 큰 비용

---

코드

import java.io.*;
import java.util.*;

// 도시 분할 계획
public class boj_1647 {
    static int N, M;
    static int[] unf;

    static class Edge implements Comparable<Edge> {
        int a, b, cost;

        public Edge(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }

    static int find(int v) {
        if (v == unf[v]) return v;
        return unf[v] = find(unf[v]);
    }

    static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) unf[fb] = fa;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        List<Edge> edges = new ArrayList<>();
        for (int i = 1; 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());

            edges.add(new Edge(A, B, C));
        }

        Collections.sort(edges);

        unf = new int[N + 1];
        for (int i = 1; i <= N; i++) unf[i] = i;

        int total = 0;
        int maxCost = 0;
        for (Edge e : edges) {
            if (find(e.a) != find(e.b)) {
                union(e.a, e.b);
                total += e.cost;
                maxCost = e.cost;
            }
        }

        System.out.println(total - maxCost);
    }
}