[백준/1717][Java] 집합의 표현 - 유니온 파인드 예제

문제

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

풀이

유니온 파인드의 연습 문제

UNION

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음

	private static void union(int a, int b) {
		//union 연산: 대표 노드까지 연결하기
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}

FIND

두 노드가 같은 집합에 속해 있는지 확인 - 특정 노드 a에 관해 a가 속한 집합의 대표 노드 반환

재귀를 이용.

	private static int find(int a) {
		//재귀 함수의 형태로 구현 -> 경로 압축 부분
		if(a == parent[a])
			return a;
		else return parent[a] = find(parent[a]);
	}

코드

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

public class B1717_집합의표현 {
	public static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		parent = new int[n + 1];
		// 대표 노드 자기 자신으로 초기화
		for (int i = 0; i <= n; i++)
			parent[i] = i;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int question = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(question == 0) union(a,b);
			else {		
				if(checkSame(a,b)) sb.append("YES").append("\n");
				else sb.append("NO").append("\n");
			}
			
		}
		System.out.println(sb);
	}

	private static boolean checkSame(int a, int b) {
		//두 원소가 같은 집합인지 확인하기
		a = find(a);
		b = find(b);
		return a==b;
	}

	private static void union(int a, int b) {
		//union 연산: 대표 노드까지 연결하기
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}

	private static int find(int a) {
		//재귀 함수의 형태로 구현 -> 경로 압축 부분
		if(a == parent[a])
			return a;
		else return parent[a] = find(parent[a]);
	}

}