[백준] 1647번 - 도시 분할 계획 [Java]

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

 

[백준] 1647번 - 도시 분할 계획 [Java]

[백준] 1647번 - 도시 분할 계획 [Java]

---

1.  아이디어

 

마을을 두 개의 분리된 마을로 두면서 남은 길의 유지비의 합이 최소가 될 때는 마을이 최소 스패닝 트리를 이루기 직전일 때다.

---

2. 문제풀이

 

마을이 최소 스패닝 트리를 이루면 하나의 마을이면서 유지비가 최소가 되므로 여기서 가장 유지비가 많이드는 경로 하나만 없다면 마을은 두 개로 나누어진다. 이를 활용해서 크루스칼 알고리즘으로 마을을 최소 스패닝 트리로 만드는데 경로의 개수가 N - 2개일 때 종료하는 방식으로 구현했다. 다만 N이 처음부터 2일 수 있어서 평소와 달리 먼저 경로의 개수를 비교하는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int c;

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

        public int compareTo(Edge o) {
            return Integer.compare(this.c, o.c);
        }
    }

    private static int[] p;

    private static int[] make(int N) {
        int[] arr = new int[1 + N];
        for (int i = 1; i <= N; i++) arr[i] = i;
        return arr;
    }

    private static int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }

    private static void union(int x, int y) {
        p[find(y)] = find(x);
    }

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

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

        PriorityQueue<Edge> edges = new PriorityQueue<>();
        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());
            edges.add(new Edge(a, b, c));
        }

        p = make(N);

        int sum = 0;
        int cnt = 0;
        while (!edges.isEmpty()) {
            if (cnt == N - 2) break;

            Edge e = edges.poll();

            if (find(e.a) == find(e.b)) continue;

            union(e.a, e.b);
            sum += e.c;
            cnt++;
        }

        System.out.println(sum);
    }
}

---

4. 후기