[삼성 SW Expert Academy] 3289. 서로소 집합

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr

SW Expert Academy

 

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

public class Swexpert_3289 {

	static int [] parent;
	static int [] rank;
	static int [] ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		int Tc = Integer.parseInt(br.readLine());
		
		for ( int tc = 1; tc <=Tc; tc++) {
			
			st = new StringTokenizer(br.readLine()," ") ;
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			parent = new int[N+1];
			rank = new int [N+1]; // 초기값 0 으로 저장 
			ans = new int [M]; 
			int idx =0;
			// 초기값 본인이 짱으로 저장 
			for ( int i=1; i<= N; i++) {
				parent[i] = i;
			}
			
			for ( int i=0; i<M; i++) {
				// 각 연산에 대해 입력받기
				st = new StringTokenizer(br.readLine(), " ");
				int is = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				// 1이면 union
				if ( is == 0) union(a,b);
				
				// 0이면 find
				else if ( is == 1) {
					if ( find(a) == find(b)) {
						ans[idx++] = 1;
					}
					else ans[idx++] = 0;
				}
				
			}
			System.out.print("#"+tc+" ");
			for ( int i=0; i< idx ; i++) {
				System.out.print(ans[i]);
			}
			
			System.out.println();
		}
		
	}
	
	static int find(int x) {
		
		// 같으면 return x
		if ( parent[x] == x) return x ;
		
		// 다르면 또 검사
		parent[x] = find(parent[x]);
		return parent[x];
	}
	
	static void union ( int x, int y) {
		
		int px = find(x);
		int py = find(y);
		
		if( px == py) return;
		else {
			if ( rank [px] > rank [py] ) 
				parent[py] = px ;
			else if ( rank [px] < rank [py])
				parent[px] = py;
			else {
				parent[py] = px;
				rank[py] ++;
			}
		}
	}
	
}

위 이미지 중 Index를 정점으로 보고, parent[Index] 는 부모의 idex를 가리킨 다는 점이 핵심이다.

 

union 과정 중 부모의 index가 계속 변하기 때문에 Find( int x ) 의 재귀함수를 손으로 그려보며 따라가보는 연습 필요

 

추가적으로 rank 배열을 활용해서 한 방향으로 길어져서 비효율적 노드를 개선하고자 했다. - union 함수 활용