SWExpertAcademy 3289-서로소 집합(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr

SW Expert Academy

 

초기에 {1}, {2}, ... {n} 이 각각 n개의 집합을 이루고 있다.

여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

연산을 수행하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 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 이하의 자연수이며 같을 수도 있다.

[출력]

각 테스트 케이스마다 1로 시작하는 입력에 대해서 같은 집합에 속해있다면 1을, 아니면 0을 순서대로 한줄에 연속하여 출력한다.

 

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

public class Solution {
	static int N; // 원소갯수
	static int[] parents;// 부모원소 관리

	// 모든 원소를 자신의 대표자로 만듦
	private static void make() {
		parents = new int[N+1];
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}

	// a가 속한 집합의 대표자 찾기
	private static int find(int a) {
		if (a == parents[a])
			return a;
		return parents[a] = find(parents[a]);
	}

	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		// 이미 같은 집합이면 union 하지 않음
		if (aRoot == bRoot)
			return false;
		// 같은 집합이 아니라면 합치기
		parents[bRoot] = parents[aRoot];
		return true;
	}
	private static boolean uniontest(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		// 이미 같은 집합이면 union 못함
		if (aRoot == bRoot)
			return false;
		// 같은 집합이 union 가능
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			sb.append("#" + t + " ");
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			make();
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int oper = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				switch (oper) {
				//oper = 0이면 합집합 연산
				case 0:
					union(a, b);
					break;
				//oper = 1이면 합집합 가능 여부 판단 뒤 sb 출력 더해줌
				case 1:
					if(uniontest(a, b)) sb.append(0);
					else sb.append(1);
					break;
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

 

operation이 0이면 합집합 연산을 진행하는 union을,

1이면 합집합 가능 여부만을 판단하는 uniontest를 불러주었습니다.

 

합집합 연산은

먼저 모든 원소를 자신의 대표자로 만들어 초기화된 parents 배열에 (=make())

각각의 원소가 속한 집합의 대표자(=find(a))가 같지 않으면 두 집합을 합치고, 나중 원소의 대표자를 먼저 원소의 대표자로 바꾸어 주었습니다.(=union(a,b))