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

문제 풀이 날짜: 2023.08.23
포스트 작성일: 2023.08.26

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 3289번: 서로소 집합 (D4)

 

키워드

유니온 파인드

 

풀이 접근법

• 집합의 연산(합집합, 트리의 부모 찾기)을 구현하는 기본적인 문제이다.
• 유니온 파인드 알고리즘은 크게 makeSet(), union(), find() 세 함수로 나눠 구현한다.
  
• makeSet()
  • 자기만을 원소로 갖는 단위 서로소 집합을 생성한다. parents가 자기 자신을 가리키게 만들면 된다.
• union()
  • 두 원소의 부모가 같지 않다면 같은 집합으로 합친다.
  • 집합을 합치는 것은 한 노드(a)의 부모를 나머지 노드(b) 또한 부모로 가리키도록 만들어주면 된다. (같은 부모를 가리킴)  
• find()
  • 어떤 노드 a의 부모를 재귀적으로 찾는다.
  • 매개변수로 들어온 노드가 부모로 자기 자신을 가리키면 그것이 하위 노드의 부모로 리턴시킨다.

 

코드

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

public class Solution {

	private static int N;
	private static int M;
	
	private static int[] parents;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			
			String[] temp = br.readLine().split(" ");
			
			N = Integer.parseInt(temp[0]);
			M = Integer.parseInt(temp[1]);
			
			makeSet();
			
			sb.append("#").append(test_case).append(" ");
			StringTokenizer st;
			for(int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				
				int ope = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(ope == 0) {
					union(a, b);
				} else if (ope == 1) {
					if(find(a) == find(b)) {
						sb.append(1);
					} else sb.append(0);
				}
			}
			
			sb.append("\n");
		}

		System.out.println(sb);
	}
	
	private static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot == bRoot) return; //두 요소가 같은 집합에 속해있다면
		
		//bRoot 이하의 집합을 aRoot 아래로 붙인다.
		parents[bRoot] = aRoot;
	}
	
	private static int find(int a) {
		if(a == parents[a]) return a;
		
		parents[a] = find(parents[a]);
		
		return parents[a];
	}
	
	// 모든 요소는 자기만을 원소로 갖는 단위 서로소 집합임.
	private static void makeSet() {
		parents = new int[N + 1];
		for(int i = 0; i <= N; i++) {
			parents[i] = i;
		}
	}

}

---

 

 

git 링크

(git 링크 첨부)