[SWEA/Java] 3289. 서로소 집합

[SWEA/Java] 3289. 서로소 집합

SW Expert Academy

---

문제 해석

서로소 집합 문제는 주어진 집합에 대해 특정 연산(합집합, 소속 확인)을 수행하는 알고리즘을 구현하는 문제다. 이 문제에서는 두 가지 연산을 지원해야 한다:

1. 두 원소가 포함된 집합을 합친다.
2. 두 원소가 같은 집합에 속하는지 확인한다.

풀이 과정

1. union-find 자료구조를 사용하여 각 원소의 대표자와 집합의 높이를 관리한다.
2. 초기화에서는 각 원소가 자신만을 포함하는 집합의 대표자가 되도록 설정한다.
3. 합집합(union) 연산은 두 원소의 대표자를 찾아, 하나의 대표자 아래에 다른 대표자를 통합하는 방식으로 진행한다. 높이가 낮은 집합을 높이가 높은 집합 아래에 통합하고, 높이가 같을 경우 한쪽의 높이를 증가시킨다.
4. 소속 확인(find) 연산은 원소의 최종 대표자를 찾는다. 이 과정에서 경로 압축을 통해 집합의 구조를 최적화한다.

코드

package edu.ssafy.im.SWEA.D4.No3289;

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

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Solution().io();
	}

	private int n;  // 집합의 원소 수
	private int m;  // 수행할 연산의 수
	private int[] set;  // 각 원소의 대표자
	private int[] height;  // 각 집합의 높이
	private StringBuilder sb = new StringBuilder();  // 결과 문자열을 저장하는 StringBuilder

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());  // 테스트 케이스 수
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			makeSet();  // 초기 집합 생성
			
			sb.append("#").append(t).append(" ");
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int c = Integer.parseInt(st.nextToken());  // 연산 종류
				int a = Integer.parseInt(st.nextToken()) - 1;  // 원소 1
				int b = Integer.parseInt(st.nextToken()) - 1;  // 원소 2
				doCommand(c, a, b);  // 연산 수행
			}
			sb.append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	private void makeSet() {  // 각 원소를 자기 자신의 대표자로 초기화
		set = new int[n];
		height = new int[n];
		for (int i = 0; i < n; i++) {
			set[i] = i;
			height[i] = 0;
		}
	}
	
	private void doCommand(int c, int a, int b) {  // 주어진 연산 수행
		switch (c) {
		case 0:  // union 연산
			unionSet(a, b);
			break;
		case 1:  // find 연산
			if(findSet(a) == findSet(b)) {
				sb.append(1);
			} else {
				sb.append(0);
			}
			break;
		}
	}
	
	private int findSet(int org) {  // 경로 압축을 사용한 find 연산
		if (set[org] == org) return org;
		else return set[org] = findSet(set[org]);
	}
	
	private void unionSet(int a, int b) {  // 높이를 사용한 union 연산
		int rootA = findSet(a);
		int rootB = findSet(b);
		
		if(rootA != rootB) {
			if(height[rootA] > height[rootB]) {
				set[rootB] = rootA;
			} else {
				set[rootA] = rootB;
				if(height[rootA] == height[rootB]) height[rootB]++;
			}
		}
	}
}

시간 복잡도 분석

union-find 알고리즘은 경로 압축과 함께 사용할 때 거의 상수 시간에 가까운 find 연산을 제공한다. union 연산도 find 연산을 기반으로 하므로, 각 연산의 평균적인 시간 복잡도는 거의 상수 시간이다. 따라서 전체 시간 복잡도는 주어진 연산 수 m에 비례하며, O(m)이다.

느낀점

서로소 집합 자료구조는 그래프 알고리즘뿐만 아니라 다양한 알고리즘 문제에서 중요하게 사용되는 기본적인 자료구조 중 하나다. 이 문제를 통해 union-find 구조를 효과적으로 구현하고 활용하는 방법을 더 잘 이해할 수 있었다.