[BOJ 백준] 집합의 표현(1717) Java

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

1717번: 집합의 표현

 

문제 설명 : 

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

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

 

입력 : 

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

 

출력 : 

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

예제 입력 : 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

 

예제 출력 : 

NO
NO
YES

 

접근법 : 

1) 어떻게 풀 것인가?

N이 100만으로 제법 큰 편이고, M도 10만으로 적지 않다.

 

Naive하게 각 집합을 하나의 Node로 생각하고 트리로 구성하게 될 경우 

Worst Case에서 Time out이 발생할 수 있다.

 

왜냐하면 극단적으로 linked list의 편향된 트리를 구성한다면 

한 번 같은 집합인지 아닌지 확인할때 N에 가까운 시간 복잡도가 소요되고, 

M이 10만으로 제법 크기때문에 O(M*N)에 가까운 수가 발생해 Time out이 발생할 수 있다.

 

이럴때 쓰기 좋은 알고리즘으로 유니온 파인드, 또는 서로소 집합이 있다.

 

요약하면,

① 1~N까지 1차원 배열에 처음에 각자 자신의 숫자를 세긴다. 이 배열을 편의상 parent(조상) 배열이라고 한다.

     → N개의 서로 다른 집합. 서로소 집합 (disjoint set) 이 존재

② 서로 다른 2개 집합의 parent(조상)을 확인할 경우 재귀 함수를 활용해 찾는다.

③ 합쳐야 되는 경우 a, b 각자의 parent(조상)을 찾아 하나로 통일한다.

 

 

위의 로직을 코드로 구현하면 아래와 같다. 

① 초기화 - 최초 N을 입력받고 각자 자기 자신이 하나의 집합을 구성하도록 자기 자신을 parent 배열에 기록

// 1 ~ N 까지의 int 배열
int[] parent = new int [N+1];

for (int i = 1; i<= N; i++) {
			// 자신의 id를 parent에 기록 → 1~N 모두 다른 집합
			parent[i] = i;
}

② 파인드 - 특정 id의 조상을 찾기

	// id의 조상을 찾는 함수
	static int find(int id) {
		if (parent[id]==id) return id;
		return parent[id] = find(parent[id]);
	}

③ 유니온 - a, b를 하나의 집합으로

	// a와 b를 하나의 집합으로 만드는 함수
	static void union(int a, int b){
		int pa = find(a);
		int pb = find(b);
		parent[pa] = pb;		
	}

 

① 초기화 + ② 파인드(find) + ③ 유니온(union) = Union Find 완성

 

 

2) 시간복잡도

union find 는 시간 복잡도를 수학적으로 구하기 어려운 알고리즘이다.

왜냐하면 union이 먼저 얼마나 나오냐, find가 먼저 얼마나 나오냐 등에 따라 동적으로 변화하기 때문이다.

 

예를 들어 find만 10만 번 나오고 union이 마지막에 한 번 나온다면

시간복잡도는 find 1번당 O(1) / union 1번당 O(1) -> O(M)이 되기도 하고,

 

union이 5만 번 호출 되고, find가 5만 번 호출 될 경우,

union 한 번에 이미 find가 2번 이상 호출되고, 재귀 형태를 띄기 때문에, 

Worst Case를 생각하는것 조차 까다롭다.

 

즉, find를 호출할때마다 수행 시간이 변하므로 까다로운 시간 복잡도를 갖고 있는데,

실제 시간 복잡도는 O(a(N))이라고 한다. a는 애커만 함수라고 하는데 상수라고 봐도 무방하다.

(출처 - https://www.crocus.co.kr/683)

 

개인적인 경험으로 문제 조건마다 상이하지만, M log N에 가까운 복잡도가 나오는 경우가 많았다.

 

이 문제의 경우 입/출력을 10만 번 해야해서 시간은 생각보다 조금 걸렸다.

출력을 StringBuilder로 모아서 할 경우 절약될 것으로 예상 

(Java 기준 -  548ms)

 

3) 공간복잡도

N (100만) 1차원 배열로 크지 않아 특별히 고려하지 않음.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

유니온 파인드, 서로소 집합의 기본 코드 작성법.

 

Java 코드 : 

import java.io.*;
import java.util.*;


// 백준 1717 집합의 표현 
public class Main {
	
	static int N, M;		// N : 집합의 수  /  M : 연산의 수 
	
	static int type, a, b;  // type : 0 - union, 1 - find, a, b 각 입력 값
	
	static int[] parent;	// union find를 위한 배열 parent[N+1]
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		
		parent = new int [N+1];
		
		// 1. 자기 자신을 하나의 집합으로 초기화
		for (int i = 1; i<= N; i++) {
			parent[i] = i;
		}
		
		for (int i = 1; i<= M; i++) {
			st = new StringTokenizer(br.readLine());
			type = Integer.parseInt(st.nextToken());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			// 0 - 합집합일 경우 union
			if (type == 0) {
				union(a,b);
			}
			
			// 1 - 같은 집합인지 확인하는 경우
			else if (type == 1)
			{
				if (find(a)==find(b)) {
					sb.append("YES\n");
				}
				else {
					sb.append("NO\n");
				}
			}
		}
				
		bw.write(sb.toString());
		bw.flush();
		br.close();
		bw.close();
	}
	
	
	// a와 b를 하나의 집합으로 만드는 함수
	static void union(int a, int b){
		int pa = find(a);
		int pb = find(b);
		parent[pa] = pb;		
	}
	
	// a의 조상을 찾는 함수
	static int find(int id) {
		if (parent[id]==id) return id;
		return parent[id] = find(parent[id]);
	}
	
	
}