[BOJ-1717][Union-Find] 집합의 표현 -Java

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

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 집합의표현 {
	static int N, M, parents[];

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		parents = new int[N + 1];

		solve(br, bw, st);
		bw.flush();

	}

	private static void solve(BufferedReader br, BufferedWriter bw, StringTokenizer st) throws IOException {
		makeSet();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			boolean isUnion = (Integer.parseInt(st.nextToken()) == 0) ? true : false;
			int set1 = Integer.parseInt(st.nextToken());
			int set2 = Integer.parseInt(st.nextToken());

			if (isUnion) { // 합집합
				unionSet(set1, set2);
			} 
            else { // 교집합 확인해서 bw에 써주기
            	if (findSet(parents[set1])==findSet(parents[set2]))bw.write("YES" + "\n");
                else bw.write("NO" + "\n");
			}
		}
	}

	private static void unionSet(int set1, int set2) {
		set1 = findSet(set1);
		set2 = findSet(set2);

		if (set1 != set2)
			parents[set2] = set1;

	}

	private static int findSet(int set) {
		if (parents[set] == set) return set;
		else return parents[set] = findSet(parents[set]);
	}

	private static void makeSet() {
		for (int i = 0; i <= N; i++) {
			parents[i] = i;
		}
	}

}

소요시간 : 35분

 

오랜만에 union-find 문제를 풀어봤슴다.

 

makeSet : 자기 자신을 부모로 가질 수 있게 배열 초기화

findSet : 최상위 부모를 찾아서 return 해준다.

unionSet : 집합을 합쳐준다.

 

주의 사항으로는 

findSet을 할 때 

return 에  parents[set] = findSet(parents[set]) 을 통해서 값을 갱신하면서 찾아줘야 시간초과가 나지 않습니당~

 

음... 딱히 설명할게 없는 것 같아서 요렇게 끝내겠슴다..ㅎㅎ

 

끝~