[정보올림피아드 알고리즘] 정올 1863번 종교 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [정보올림피아드 알고리즘] 정올 1863번 종교 자바(Java)

1) 문제번호 : 1863번

 

2) 문제 출처

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

JUNGOL

 

2. 문제

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

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

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

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

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

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

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

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

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

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

3. 제약사항

- 

4. 입력

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

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

 

5. 출력

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

 

6. 풀이

- 여기서 Scanner를 사용하면 시간초과(Time Limit Exceed)가 난다.

- 그래서, BufferedReader를 사용해야 한다.

- 스택오버플로우가 발생하면 union(a,b) <-> union(b,a)로 바꿔서 제출하거나, rank를 사용해야 한다.

- rank는 붙이는 트리가 기존 트리의 랭크와 같다면 기존 트리를 1씩 증가하면서 랭크를 구분하여 union을 해준다.

7. 소스 코드

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


public class Main {
	static int n; //학생 수
	static int m; //쌍의 수
	static int[] arr; //make 배열
	static int[] rank; // 트리 깊이
	static int count=0; // 종교 개수

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); //학생 수 
		m = Integer.parseInt(st.nextToken()); //쌍의 수
		arr = new int[n+1]; //make 배열
		rank = new int[n+1]; //트리 깊이
		
		//set 만들기
		make_set();
		
		//쌍 입력받아 union 해주기
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			union(a,b);
		}
		
		for(int i=1;i<=n;i++) {
			if(arr[i]==i) count++;
		}
		
		System.out.println(count);

	}
	
	//make_set
	public static void make_set() {
		for(int i=1;i<=n;i++) arr[i] = i;
	}
	
	//find_set
	public static int find_set(int a) {
        if(arr[a] == a) return a;
        return arr[a] = find_set(arr[a]);
    }
	
	//union_set
	public static void union(int a, int b) {
		int aRoot = find_set(a); 
		int bRoot = find_set(b); 
		
		//aRoot의 랭크가 bRoot보다 작다면
		if(rank[aRoot]<rank[bRoot]) arr[aRoot] = bRoot;
		
		//aRoot의 랭크가 bRoot보다 크다면
		else {
			arr[bRoot] = aRoot;
			//트리를 붙인 후에 랭크가 같으면 aRoot의 랭크를 1 증가
			if(rank[aRoot]==rank[bRoot]) rank[aRoot]++;
		}
	}
}

---