백준 28118 - 안전한 건설 계획

문제

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

리뷰

유니온 파인드 연산을 통해 풀이할 수 있는 간단한 문제였다.

주어진 문제 조건에서 이미 연결 경로가 존재하는 기둥 사이에는 작업에 비용이 필요하지
않다. 따라서 유니온 파인드 연산을 통해 빔이 존재하는 기둥들간 관계를 처리해주고
빔이 존재하지 않는 기둥들간 연결 비용(서로 다른 루트로 구성된 분리 집합간 연결 개수)을
카운팅해주면 답을 도출할 수 있다.

로직의 시간복잡도는 빔을 처리하는 부분의 $O(Ma(N))$으로 수렴하므로 $N=40$인 최악의
경우에도 무난히 제한 조건 2초를 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;

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

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        int u, v, r1, r2;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            r1 = find(u);
            r2 = find(v);

            if (r1 == r2) continue;

            if (parent[r1] < parent[r2]) {
                parent[r1] += parent[r2];
                parent[r2] = r1;
            } else {
                parent[r2] += parent[r1];
                parent[r1] = r2;
            }
        }

        int cost = 0;
        for (int i = 1; i < parent.length; i++) {
            if (parent[i] < 0) cost++;
        }

        System.out.println(cost == 0 ? 0 : cost - 1);
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

}

결과