백준 1717번: 집합의 표현 [JAVA]

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

1717번: 집합의 표현

• 풀이

유니온 파인드 알고리즘을 쓰는 문제이다.

초기에는 0부터 n까지 각각의 숫자만 담은 집합이기 때문에, 부모 배열에 자기 자신을 넣는다.

부모를 찾는 find 함수와 두 원소의 부모를 합치는 union 함수를 만든다.

find 함수의 경우, 부모노드가 자기자신인 루트노드를 찾을 때까지 재귀하는 형태이다.

union함수의 경우 원소 두 개의 부모를 각각 찾아서 더 작은 쪽을 큰 쪽에 넣는 형태이다.

• 코드

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

public class Main {
	static int N, M;
	static int parent []; 
	
	// x의 부모를 찾는 연산
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
 
    // y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		parent = new int[N+1];
		
		for (int i=0; i<N+1; i++) parent[i] = i; // 자기 자신으로 부모 초기화
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(bf.readLine());
			int sel = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			// 합집합
			if (sel==0) {
				union(a,b);
			}
			
			// 확인 연산
			else {
				if(find(a)==find(b)) System.out.println("YES");
				else System.out.println("NO");
			}
		}

	}
}