[SWEA/Java] 7465. 창용 마을 무리의 개수

[SWEA/Java] 7465. 창용 마을 무리의 개수

SW Expert Academy

---

문제 해석

이 문제는 마을 사람들 사이의 관계를 주어진 관계들을 통해 무리를 형성하고, 이들 무리의 수를 계산하는 문제이다. 사람들이 어떻게 연결되어 있는지 그래프로 표현하고, 이 그래프에서 서로 연결된 집합의 개수를 찾아내는 것이 핵심이다.

풀이 과정

1. 각 사람을 하나의 노드로 간주하고, 주어진 관계를 양방향 그래프로 표현한다.
2. Union-Find 자료구조를 사용하여 각 사람이 속한 집합을 관리한다.
3. 주어진 관계를 통해 두 사람을 연결하며 union 연산을 수행한다.
4. 모든 연결 처리 후, 각 노드의 루트 노드를 찾아서 (find 연산을 통해) 서로 다른 루트 노드의 수를 세어 무리의 수를 계산한다.

코드

package edu.ssafy.im.SWEA.D4.No7465;

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

public class Solution {
    private int n;  // 마을 사람 수
    private int m;  // 관계 수
    private int[] set;  // 각 사람의 집합을 관리하는 배열
    private int[] height;  // 집합의 트리 높이

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

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());  // 테스트 케이스 수
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            makeSet();  // 초기 집합 생성

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;
                unionSet(a, b);  // 두 사람을 하나의 집합으로 연결
            }

            sb.append("#").append(t).append(" ").append(countSet()).append("\n");  // 무리의 수 계산
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void makeSet() {  // 초기 집합 생성 함수
        set = new int[n];
        height = new int[n];
        for (int i = 0; i < n; i++) {
            set[i] = i;  // 자기 자신을 대표로 설정
        }
    }

    private int findSet(int org) {  // 대표를 찾는 함수 (경로 압축 포함)
        if (set[org] == org) return org;
        else return set[org] = findSet(set[org]);
    }
    
    private void unionSet(int org, int target) {  // 두 요소를 하나의 집합으로 합치는 함수
        int a = findSet(org);
        int b = findSet(target);
        
        if (a != b) {
            if(height[a] > height[b]) {
                set[b] = a;
            } else {
                set[a] = b;
                if(height[a] == height[b]) height[b]++;
            }
        }
    }
    
    private int countSet() {  // 각 집합의 대표자를 카운팅하여 무리의 수를 계산하는 함수
        int[] cntArr = new int[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            findSet(i); // 모든 자식을 1레벨로 레벨링
        }
        for (int i = 0; i < n; i++) {
            cntArr[set[i]]++;
        }
        for (int i = 0; i < n; i++) {
            if(cntArr[i] != 0) cnt++;
        }
        return cnt;
    }
}

시간 복잡도 분석

이 알고리즘은 Union-Find 자료구조를 사용하며, union과 find 연산은 거의 상수 시간에 가까운 복잡도를 가진다 (경로 압축 및 union by rank 사용 시). 따라서 전체적인 시간 복잡도는 관계 수 m에 대해 O(mα(n))이며, 여기서 α(n)은 아커만 함수의 역함수로 매우 느리게 증가하는 함수이다.

느낀점

이 문제는 Union-Find 자료구조의 기본적인 활용을 요구하며, 이를 통해 주어진 그래프에서 연결된 컴포넌트의 수를 효과적으로 계산할 수 있다. 문제 해결을 위해 각각의 요소들이 어떤 집합에 속하는지 관리하는 방법을 이해하고 구현하는 것이 중요하다.