[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 를 출력해도 된다)

 

문제풀이

전형적인 union-find 문제인데 의문이 드는 점이 발생했다. 아래의 소스코드를 보면 알겠지만, 나는 find 부분을 아래와 같이 작성하였다.

    // 방법1
    public static int find(int p) {
		if(p == group[p]) return p;
		return group[p] = find(group[p]);
	}

해당 부분을 보면 return 에 group[p] 에 값을 할당하고 넣는 방식으로 하였더니 맞았고, 아래와 같이 find(group[p])만 입력했을때는 65%에서 계속 시간초과가 떠서 이유를 잘 이해할 수 없었다.

	// 방법2
    public static int find(int p) {
		if(p == group[p]) return p;
		return find(group[p]);
	}

도대체 두개의 코드의 차이점이 무엇이길래 이런 결과가 발생한걸까? 이를 알아보니 경로 압축 최적화라는게 진행되어서 그렇다고 한다. 경로 압축 최적화라는게 무엇일까? 이는 트리의 구조와 관련이 있는데, 경로 압축이라는게 모든 경로를 거쳐서 부모 노드를 찾는게 아니라 하나의 그룹에 속한 노드들은 모두 최상위의 노드로 표현하는 것을 의미한다는 점을 알게되었다. 

 

좌 : 방법2 / 우 : 방법 1 트리구조

비방법 2을 쓰게되면 트리의 구조가 길어지는 반면, 방법 1을 사용하면 트리의 길이가 짧아지고 한쪽으로 치우친 트리의 경우 빠른 탐색이 가능하다는 점을 깨달았다.

 

소스코드

package boj_1717_집합의표현;

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[] group;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		group = new int[N+1];
		for (int i = 0; i <= N; i++) {
			group[i] = i;
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int m = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(m == 0) union(a, b);
			else {
				int p1 = find(a);
				int p2 = find(b);
				
				if(p1 == p2) System.out.println("YES");
				else System.out.println("NO");
			}
		}
	}
	
	public static void union(int a, int b) {
		int p1 = find(a);
		int p2 = find(b);
		
		if(p1 < p2) group[p2] = p1;
		else group[p1] = p2;
	}
	
	public static int find(int p) {
		if(p == group[p]) return p;
		return group[p] = find(group[p]);
	}
}