[SWEA] - 서로소 집합 / 3289번 (Java)

[SWEA] - 서로소 집합 / 3289번 (Java)

[SWEA] - 서로소 집합 / 3289번 (Java)

1. 문제 접근

총 n개의 단일 원소를 갖는 집합에 대해 `0`(두 집합을 합치기), `1`(두 집합이 거로 같은 집합에 속하는지) 연산을 실행하고 `1`번 연산에 대해 결과를 출력하면 된다.

 

기본적인 Union Find 알고리즘이다.

 

Union Find에는 총 3개의 연산이 존재한다

1. `makeSet()`: 초기 집합 상태를 만드는 연산
2. `union()`: 두 집합을 하나의 집합으로 합치는 연산
3. `getRoot()`: 특정 노드의 집합을 식별하는 연산

따라서 `0`번 입력이 들어오면 `union()`을, `1`번 연산이 들어오면 `getRoot()`연산을 통해 결과를 얻으면 된다.

 

switch (op) {
case UNION:
    union(node1, node2);
    break;
case IS_SAME_SET:
    int node1Root = getRoot(node1);
    int node2Root = getRoot(node2);
    if(node1Root == node2Root) {
        localSb.append(1);
    }else {
        localSb.append(0);
    }
    break;
}

 

추가적으로 Union Find 알고리즘을 실행할 때, 경로 압축(Path Compression)을 통해 최적화를 진행하였다.

 

// 매개변수 node의 root를 찾는 메소드
private static int getRoot(int node) {
    if (parents[node] == node) return node;
    else return parents[node] = getRoot(parents[node]); // 경로 압축
}

---

2. 코드

package swea;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * [SWEA] - 서로소 집합 / 3289번 (Java)
 * @author JinHxxxxKim
 * 
 * 1. 테스트 케이스의 수 TC를 입력받는다.
 * 2. n(1≤n≤1,000,000), m(1≤m≤100,000)을 입력받는다.
 * 		n: 노드의 개수, m: 연산의 개수
 * 		- Make-Set() 연산 실행
 * 3. m개의 연산에 대해 반복
 * 		- 1: 두 집합의 대표자를 찾고 같다면 1을 append, 아니라면 0을 append
 * 		- 0: 두 집합에 대해 union 연산을 실행한다.
 * 4. 출력
 */
public class Sol_3289 {
	private static final int UNION = 0;
	private static final int IS_SAME_SET = 1;
	
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;
	
	private static int N, M;
	
	// 각 노드의 부모(대표자)를 저장하는 배열
	private static int[] parents;
	
	
	public static void main(String[] args) throws Exception {
		int TC = Integer.parseInt(br.readLine().trim());
		for (int testCase = 1; testCase <= TC; testCase++) {
			StringBuilder localSb = new StringBuilder();
			st = new StringTokenizer(br.readLine().trim());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			parents = new int[N+1];
			
			// Make-Set 연산
			for(int node = 1;node<=N;++node) {
				parents[node] = node;
			}
			
			// 연산 시작
			for (int opCnt = 0; opCnt < M; ++opCnt) {
				st = new StringTokenizer(br.readLine().trim());
				int op = Integer.parseInt(st.nextToken());
				int node1 = Integer.parseInt(st.nextToken());
				int node2 = Integer.parseInt(st.nextToken());
				
				switch (op) {
				case UNION:
					union(node1, node2);
					break;
				case IS_SAME_SET:
					int node1Root = getRoot(node1);
					int node2Root = getRoot(node2);
					if(node1Root == node2Root) {
						localSb.append(1);
					}else {
						localSb.append(0);
					}
					break;
				}
			}
			sb.append(String.format("#%d %s\n", testCase, localSb.toString()));
		}
		System.out.println(sb);
	}

	// 두 집합을 합치는 메소드
	private static void union(int node1, int node2) {
		int node1Root = getRoot(node1);
		int node2Root = getRoot(node2);
		
		parents[node1Root] = node2Root;
	}

	// 매개변수 node의 root를 찾는 메소드
	private static int getRoot(int node) {
		if (parents[node] == node)
			return node;
		else
			return parents[node] = getRoot(parents[node]); // 경로 압축
	}
}

---

3. 디버깅

각 노드의 대표자(root)를 찾을 때, 경로 압축(Path Compression)을 통해 최적화를 진행하고, Union 연산 실행 시, 매개변수로 전달 받은 노드의 부모(`parent`)를 수정하는 것이 아닌, 해당 노드의 대표자(root)의 부모를 수정하는 부분이 중요하다.

---

4. 결과