[SWEA] 7465번 창용 마을 무리의 개수 (JAVA)

SW Expert Academy

기본적인 Union-Find 문제이다.

좀 더 효율적인 비교를 위해

union 연산에서 트리의 깊이(rank)를 이용하여

rank가 더 높은 집합에 rank가 낮은 집합을 붙이게 하였다.

rank가 같을 때는 어쩔 수 없이

둘 중 하나는 증가돼야 하므로 + 1 해주었다.

 

rank가 다를 때

 

 

rank가 동일할 때

 

import java.util.Scanner;

public class D4_7465_창용마을_무리의개수 {
	static int T, N, M, res;
	static int parentOf[], rank[];
	
	static int find(int a) {
		if(parentOf[a] == a) return a; // 자기 자신을 가리키면 부모를 찾은 거임
		return parentOf[a] = find(parentOf[a]);
	}
	
	static void union(int a, int b) {
		int parentOfA = find(a), parentOfB = find(b);
		if(rank[parentOfA] < rank[parentOfB]) { // 랭크(깊이)가 더 큰 집합에 작은 애가 붙음
			parentOf[parentOfA] = parentOfB;
			return;
		}
		if(rank[parentOfA] == rank[parentOfB]) rank[parentOfB]++; // 랭크가 같으면 하나는 + 1 해주어야 함
		parentOf[parentOfB] = parentOfA;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			N = sc.nextInt(); M = sc.nextInt(); res = 0;
			parentOf = new int[N + 1]; rank = new int[N + 1];
			for(int i = 1; i <= N; i++) parentOf[i] = i; // 자기 자신을 가리키게 초기화
			for(int i = 0; i < M; i++) union(sc.nextInt(), sc.nextInt());
			for(int i = 1; i <= N; i++) if(parentOf[i] == i) res++; // 자기 자신을 가리키면 집합 하나라는 뜻
			System.out.println("#" + t + " " + res);
		}	
	}
}