[백준/Java] 1717 집합의 표현

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

문제 요약

초기에 {0}, {1}, ..., {n}와 같은 꼴의 n+1개 집합이 있다.
여기에 m개의 연산을 수행하여 그 결과를 출력하고자 한다. 이는 m개의 줄로 주어진다.
"0 a b"의 형태는 a가 포함된 집합과 b가 포함된 집합을 합치는 것이다.
"1 a b"의 형태는 a와 b가 같은 집합에 포함되어 있는지 확인하는 것이다. 이때 "YES" 또는 "NO"를 출력한다.
n은 최대 100만, m은 최대 10만, a와 b는 0이상 n이하이며 둘이 같을 수 있다.

---

문제 접근

union-find를 이용하여 문제를 해결할 수 있다.
union 연산과 find 연산만 잘 설계하면 된다.

union 연산은 두 집합을 하나의 집합으로 합치는 것이다. 하나의 집합이라는 것은 그 집합의 모든 원소가 하나의 루트 값을 가리키게 하여 같은 루트 값을 갖는 것들의 모임으로 정의할 수 있다.

find 연산은 두 집합이 같은 집합인지 파악하는 것이다. 집합을 합칠 때부터 모든 원소가 하나의 루트를 가리키도록 업데이트했다면 단순히 루트 값을 비교하여 바로 알 수 있겠지만, 트리가 여러 경로로 존재할 수 있기 때문에 union 연산에서는 이를 수행할 수 없다.
그래서 find 연산에서 부모 노드를 따라가며 루트 노드가 동일한지 파악해야 하는데, 루트 찾기와 갱신을 한 번에 수행해서 연산 시간을 줄일 수 있는 테크닉도 사용할 수 있다.

0부터 n까지 모두 사용하므로 편하게 배열 크기를 n+1로 만들자.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (추가 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	static int n, m;
	static int[] parent;
	
	// 해당 노드의 루트를 찾는 함수
	// 찾는 것과 동시에 그 경로의 모든 부모들이 바로 루트를 가리키게 만들어 다음 연산의 시간을 아낄 수 있다.
	public static int find(int a) {
		if (parent[a] == a) return a;
		else return parent[a] = find(parent[a]);
	}
	
	// a의 루트가 b의 루트를 가리키게 만들어 두 입력을 같은 집합으로 만든다.
	public static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		parent[rootA] = rootB;
	}
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st1.nextToken());
        m = Integer.parseInt(st1.nextToken());
        
        // 각 집합의 root 초기화
        parent = new int[n+1];
        for (int i = 0; i < n+1; i++) {
        	parent[i] = i;
        }
        
        // 입력을 받으며 연산 수행
        for (int i = 0; i < m; i++) {
        	StringTokenizer stm = new StringTokenizer(br.readLine());
        	
        	int order = Integer.parseInt(stm.nextToken());
        	int a = Integer.parseInt(stm.nextToken());
        	int b = Integer.parseInt(stm.nextToken());
        	
        	// 합 연산인 경우
        	if (order == 0) {
        		union(a, b);
        	}
        	// 같은 집합 여부 판단인 경우
        	// 루트가 같다면 같은 집합에 존재한다.
        	// 이때는 결과 출력을 추가해주어야 한다.
        	else if (order == 1) {
        		if (find(a) == find(b)) sb.append("YES\n");
        		else sb.append("NO\n");
        	}
        }
        
        // 정답 출력
        System.out.println(sb);
    }
}

---

회고

(추가 예정)