[백준 / Java] 1717번: 집합의 표현 (골드5)

문제 풀이 날짜: 2023.09.18
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1717번: 집합의 표현 (골드5)

 

키워드

유니온 파인드

 

풀이 접근법

• 유니온 파인드의 기초적인 구현을 묻는 문제이다.
• 합집합 연산은 union 함수, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 find 함수가 수행한다.
• 정확한 연산을 위해 트리의 깊이인 rank 배열을 선언한다.
  • 합집합 연산을 수행할 때마다 트리의 다음 레벨에 노드를 붙이게 되므로 rank를 증가시킨다.

 

코드

import java.io.*;

public class Main {
	
	private static int[] root;
	private static int[] rank; 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]); 
		
		root = new int[n + 1];
		rank = new int[n + 1];
		for(int i = 0; i <= n; i++) {
			root[i] = i;
			rank[i] = 0;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < m; i++) {
			temp = br.readLine().split(" ");
			
			int operation = Integer.parseInt(temp[0]);
			int a = Integer.parseInt(temp[1]);
			int b = Integer.parseInt(temp[2]);
			
			if(operation == 0) {
				union(a, b);
			}
			else if(operation == 1) {
				boolean result = isSameSet(a, b);
				
				if(result) {
					sb.append("YES").append('\n');
				}
				else {
					sb.append("NO").append('\n');
				}
			}
			else {
				continue;
			}
		}
		
		System.out.print(sb);
	}
	
	public static int find(int x) {
		if(root[x] == x) {
			return x;
		}
		else {
			return root[x] = find(root[x]);
		}
	}
	
	public static void union(int x, int y) {
		x = find(x); 
		y = find(y);
		
		if(x == y) {
			return;
		}
		
		if(rank[x] < rank[y]) {
			root[x] = y;
		}
		else if(rank[x] >= rank[y]) {
			root[y] = x;
		}
		
		if(rank[x] == rank[y]) {
			rank[x]++;
		}
	}
	
	public static boolean isSameSet(int x, int y) {
		x = find(x);
		y = find(y);

		return (x == y);
	}
}

 

---

 

git 링크

(git 링크 첨부)