백준 | 1717번. 집합의 표현 - 유니온 파인드 문풀

⬛ 백준 1717번. 집합의 표현 - 유니온 파인드 문풀

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

1717번: 집합의 표현

문제

초기에 n+1 개의 집합이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n,m 이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은0, a, b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1, a, b 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

---

💚 문제 접근 방식

• 두 원소가 같은 집합에 포함되어 있는지를 확인하는 문제라는 점에서 전형적인 ‘유니온 파인드’임을 알 수 있다.
• 유니온 파인드는 보통 사이클 여부를 확인하거나, 동일 집합 여부를 판단할 때 많이 활용하는 알고리즘 이기 때문

1) parent[] 1차원 배열 (자기 자신으로 초기화) : 이후 대표 노드가 담길 용도이다.

2) union(a, b) 정의 : a와 b이 대표노드가 다르다면 동일 집합 소속으로 만듬

3) find(a) 정의 : a에 대한 대표 노드를 찾을 때까지 재귀해서 리턴

4) 질의에 따른 합집합 union 처리와 소속 여부 판별 후 출력

풀이 설명 그림

---

💚 제출 코드

import java.util.Scanner;

/**
 * 1717번. 집합의 표현 - 유니온 파인드 문풀 
 * @author MYLG
 *
 */
public class Main {
	static int[] parent;//대표 노드 저장용 배열 
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();//정점 개수
		int M = kb.nextInt(); //질의 
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i]= i;//초기화 
		
		for(int i=0; i<M; i++) {
			int query = kb.nextInt();
			int a = kb.nextInt();
			int b = kb.nextInt();
			if(query == 0) { //합집합 연산 수행 
				union(a, b);
			}else if(query == 1) { //ㄹㅇ 질의
				if(find(a) == find(b)) {
					System.out.println("YES");
				}else {
					System.out.println("NO");
				}
			}
		}	
	}
}

---

💚 후기

-예전에 풀었던 문제를 다시 풀게 됐다.

- 유니온 파인드의 시간 복잡도는 최적화 여부나 순서에 따라 매번 달라서 엄격히 구하기는 어렵다고 되어 있지만, 

경로 압축으로 최적화 한 경우, 시간 복잡도는 O(α(N)) 정도라고 한다.
α(x)는 애커만 함수라고 하는데, x가 2의 65536제곱일 때 함수 값이 5가 되는 함수여서 매우 작다고 함

이 문제에서는 parent[] 초기화 시 O(N) 이 소요되고 각각의 질의 수행에서의 (union과 find)가 O(a(N)) 정도를 갖는다고 하는데 질의를 총 M번 수행하니까 M * O(a(N)) 이 전체 시간 복잡도가 된다고 한다.
따라서, N이 최대 1,000,000 이고, M이 최대 100,000 이기 때문에 이 문제는 최악에서도 대략 O(100,000) 의 시간 복잡도를 가져서 시간 내에 작동할 수 있다고 한다.
(애커만 함수는 아주 작은 값으로 수렴하기 때문에 거의 상수에 가까워진다고 보므로)