[백준] 1647번 - 도시 분할 계획 (Gold 4)

문제 링크

백준 1647번 - 도시 분할 계획 (Gold 4)

문제 설명

N개의 집과 그 집들을 양방향으로 연결하는 M개의 길로 이루어진 마을이 있다.
마을을 두 개로 쪼개면서 길을 없애고자 하는데, 각 마을 내부의 모든 집은 서로 연결되어 있어야 한다.
각 길의 유지비가 주어져있을 때, 마을을 둘로 쪼갰을 때 가능한 총 유지비의 최솟값을 구하시오.

정답 코드 및 설명

최소 신장 트리에서 가장 긴 간선을 빼면 조건을 만족하는 마을 두 개로 분할된 것이다.
최소 신장 트리를 구하는 대표적인 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있다.
간선이 빽빽할 때는 프림 알고리즘이, 별로 없을 때는 크루스칼 알고리즘이 적절하다.

자세한 알고리즘은 다음에 따로 포스팅할 예정이라, 여기서는 각 알고리즘에 대해 간략하게만 소개하도록 하겠다.
먼저, 프림 알고리즘은 다익스트라와 유사한 방식을 따른다.
다익스트라는 노드들의 값을 시작 정점으로부터의 최단 거리로 갱신한다면, 프림에서는 이미 탐색한 점들의 집합에서부터의 최단 거리로 갱신한다는 점이 유일한 차이점이다.
따라서 프림 알고리즘의 시간 복잡도는 다익스트라와 동일한 $O(E\log V)$이다.

크루스칼 알고리즘은 가장 가중치가 적은 간선부터 차례로 더해나가는 방식을 택한다.
처음에는 모든 점이 각각 독립된 집합으로 있다가, 간선이 추가될 때마다 각 점에 해당하는 집합을 합쳐준다.
집합을 합치는 과정은 유니온 파인드 알고리즘을 활용하면 된다.
택한 간선에 있는 두 점이 이미 이어진 상태라면, 그 간선은 건너뛴다.
이 과정을 모든 점이 이어질 때까지, 즉 간선 V-1개가 골라질 때까지 반복한다.
크루스칼 알고리즘의 시간 복잡도 역시 $O(E\log V)$이다.

아래 코드는 크루스칼 알고리즘을 사용하여 구현하였다.
이 문제는 최소 신장 트리가 아니라 거기에서 가장 긴 간선을 뺀 트리를 구해야한다.
따라서 크루스칼 알고리즘을 간선 V-2개가 골라질 때까지만 수행하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1647 {
    int n;
    PriorityQueue<int[]> roads;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        roads = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int[] currRoad = new int[3];
            currRoad[0] = Integer.parseInt(st.nextToken()) - 1;
            currRoad[1] = Integer.parseInt(st.nextToken()) - 1;
            currRoad[2] = Integer.parseInt(st.nextToken());
            roads.add(currRoad);
        }
    }

    int kruskal() {
        int[] set = new int[n];
        Arrays.fill(set, -1);
        int numOfRoads = 0;
        int cost = 0;
        while (numOfRoads < n - 2) {
            int[] currRoad = roads.poll();
            if (!union(currRoad[0], currRoad[1], set)) continue;
            numOfRoads++;
            cost += currRoad[2];
        }
        return cost;
    }

    boolean union(int a, int b, int[] set) {
        int aSet = findSet(a, set);
        int bSet = findSet(b, set);
        if (aSet == bSet) return false;
        if (-set[aSet] < -set[bSet]) {
            int temp = aSet;
            aSet = bSet;
            bSet = temp;
        }
        if (set[aSet] == set[bSet]) {
            set[bSet] = aSet;
            set[aSet]--;
        } else set[bSet] = aSet;
        return true;
    }

    int findSet(int a, int[] set) {
        if (set[a] < 0) return a;
        return set[a] = findSet(set[a], set);
    }

    void solution() throws IOException {
        input();
        System.out.println(kruskal());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1647().solution();
    }
}