[SWEA] D4 3289 서로소 집합 (JAVA)

문제

저작권 문제로 인해 링크만 첨부합니다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE&problemTitle=3289&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

풀이 방법

문제를 간단하게 정리하면 각 원소가 초기에 자기자신만 가지고 있는 집합을 가지고 있고, 
입력에 따라서 합집합과 같은 집합인지 확인하는 계산을 수행한다.
첫번째 원소가 0이면 합집합을 수행하고, 1이면 같은 집합인지 확인하는 연산을 수행한다.
풀이 방법은 우선 각 집합마다 부모를 정하고, 같은 집합인지 확인하는 계산을 하는 경우 부모가 같은지만 확인해서 출력하면 된다. 
합집합을 수행하는 경우에는 부모가 동일한지 보고, 동일하다면 이미 같은 집합에 속해있기 때문에 연산을 수행하지 않고, 부모가 다르다면 부모를 동일하게 맞춰줘서 합집합 연산을 수행하도록 구현했다.

 

제출 코드

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

public class D4_3289_서로소집합 {
	static int[] parents;

	static void makeSet(int N) { //각 부모를 자신으로 설정 
		parents = new int[N+1];
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}

	static void union(int a, int b) { //합집합
		int p = findParents(a);
		int q = findParents(b);
		parents[q] = p;
	}

	static int findParents(int n) { //부모 찾기
		if(parents[n] == n) return n;
		return parents[n]= findParents(parents[n]);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb;

		int T = Integer.parseInt(st.nextToken());
		for (int test_case = 1; test_case <= T; test_case++) {
			 sb = new StringBuilder();
			sb.append("#");
			sb.append(test_case);
			sb.append(" ");
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());

			makeSet(N); // 초기 세팅

			//연산 횟수만큼 반복
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int mode = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(mode == 0 ) { //합집합이면
					if(findParents(a)!=findParents(b)) {// 같은 집합이 아니면 합치기
						union(a, b );
					}
				}else { //같은 집합인지 확인하기
					if(findParents(a)==findParents(b)) sb.append("1"); //같은 집합이면
					else sb.append("0"); //아니면
				}
				
			}
			System.out.println(sb);
		}

	}
}