[Java] 1863. 종교

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1136&sca=4070

JUNGOL

문제

오늘날 아주 많은 다른 종교들이 있고 이들 모두를 추적하는 것은 어려운 일이다.

당신이 다니는 학교에서 학생들이 믿고 있는 종교가 총 몇 가지 있는가를 알고자 한다.

학교에는 n (0 < n ≤ 50,000)명의 학생이 있다.

모든 학생에게 자기가 가진 종교가 무엇인지를 물어보는 것은 힘든 일이고 

게다가 많은 학생들은 그들의 종교를 나타내는 것을 좋아하지 않는다.

이 문제를 해결하기 위한 한 가지 방법은 같은 종교를 가지는 사람들 끼리 짝을 짓도록 하는 것이다.

쌍의 수는 m ( 0 ≤ m ≤ 100,000 ) 이다. 

이 데이터로 당신은 모든 학생들이 어떤 종교를 가지고 있는가는 알지 못하지만 

학생들이 최대한 가질 수 있는 종교의 가지 수를 알 수 있다.

모든 학생들이 최대 한 가지 종교를 가지고 있다고 하자.

 

입력형식

정수 n , m 이 주어진다. 다음 m 라인은 두 정수 i , j 가 주어진다.

i, j 는 i번 학생과 j번 학생이 같은 종교를 가진 학생의 쌍이다(1≤i, j≤n).

 

출력형식

종교의 가지 수를 출력한다.

---

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

public class JUNGOL_1863 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder("");
	static int parents[], n, m;
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		parents = new int[n+1];
		make();
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int pre = Integer.parseInt(st.nextToken());
			int post = Integer.parseInt(st.nextToken());
			unionSet(pre, post);
		}
		check();
	}
	private static void check() {
		int cnt = 0;
		for (int i = 1; i < parents.length; i++) {
			if(parents[i] == i) cnt++;
		}
		System.out.println(cnt);
	}
	
	private static void unionSet(int pre, int post) {
		if(findSet(pre) == findSet(post)) return;
		parents[findSet(post)] = findSet(pre);
	}
	private static int findSet(int a) {
		if(parents[a] == a) return a;
		return parents[a] = findSet(parents[a]);
	}
	private static void make() {
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}
	}
}

 

Union-Find 알고리즘과 Path Compression을 이용하여 작성하였다.

check()메소드에서 몇번의 부분성공이 있었지만, 대표자를 찾는 방법을 본인의 인덱스와 본인의 값이 같은 경우를 생각해보는 방법으로 쉽게 해결이 되었다.