[Union-Find] 14163. 그룹 나누기 (Java)

[SWEA] 14163. 그룹 나누기

📌 풀이 과정

1. Union-Find
   각 사람을 노드로, 연결된 사람들(같은 조가 되고 싶은 사람들)을 하나의 집합으로 묶는다.

2. 연결된 사람들은 하나의 조가 되고, 연결되지 않은 사람들은 각각 단독 조가 된다.

3. 최종적으로 Union-Find를 사용해 각 사람이 속한 조의 대표를 찾고, 대표의 개수를 세어 전체 조의 수를 구한다.

✨ 제출 코드

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

class Solution {
    
    static int N;
    static int[] pair;
    
    static int findPair(int x) {
        if(pair[x] == x) return x;
        return pair[x] = findPair(pair[x]);
    }
    
    static void union(int a, int b) {
        int rootA = findPair(a);
        int rootB = findPair(b);
        
        if(rootA != rootB) {
            pair[rootB] = rootA;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            pair = new int[N+1];
            for(int i = 1; i <= N; i++) {
                pair[i] = i;
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());
                union(n1, n2);
            }
            
            int answer = 0;
            for(int i = 1; i <= N; i++) {
                if(findPair(i) == i) answer++; // 대표자의 수 = 집합의 개수
            }
            
            System.out.println("#" + t + " " + answer);
        }
    }
}