[Union-Find] 7465. 창용 마을 무리의 개수 (Java)

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

[[SWEA] 14163. 그룹 나누기] 풀이 -> union-find 유형 다른 문제

📌 풀이 과정

대표적인 Union-Find 문제 유형이다.

집합의 개수 = 대표자의 개수

이 문제에서 무리는 집합을 의미한다.
마을에 몇 개의 무리가 존재하는지 계산하는 것이므로
마지막에 대표자의 수를 구하면 된다.

하지만, 문제의 두번째 테케를 보면

parent[] 배열

idx	1	2	3	4	5	6
val	1	1	1	1	1	3

연산을 모두 끝낸 후 부모 배열을 보면 이렇게 결과가 나온다.
1, 2, 3, 4, 5, 6은 모두 한 그룹이지만, 이 상태로 정답을 그대로 결론내기엔 무리가 있다.

합집합을 하는 과정에서 값이 작은 쪽으로 루트를 줬기 때문에 아래와 같은 과정이 필요한 것이다.

int answer = 0;
			for(int i = 1; i <= N; i++) {
				if(i == parent[i]) answer++; // 대표자 개수 = 마을 개수
			}

부모 값이 자기 자신과 같은 것 = 해당 집합의 대표자
라고 생각하면 된다.

✨ 제출 코드

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

public class Solution {
	static int N, M;
	static int[] parent;
	
	static void initParent() {
		for(int i = 1; i <= N; i++) {
			parent[i] = i;
		}
	}
	
	static int findParent(int x) {
		if(x == parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	static void union(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}

	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());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			parent = new int[N + 1];
			initParent();
			
			for(int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				union(a, b);
			}
			
			int answer = 0;
			for(int i = 1; i <= N; i++) {
				if(i == parent[i]) answer++; // 대표자 개수 = 마을 개수
			}
			
			System.out.println("#" + t + " " + answer);
		}
		
		
	}

}