정올 1863 : 종교

Java

1863 : 종교

문제

n명의 학생들과 m개의 종교의 짝이 주어질때, 종교 종류의 개수를 구하라.

문제출처

접근 방법

서로소 집합을 표현하는 방법을 통하여 문제를 해결하였다.

서로소란

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조는 union, find 두가지 연산으로 이루어진다.

• union: 두개의 원소가 각각 포함되어 있는 집합을 하나로 합친다.
• find: 특정한 원소가 속한 집합이 어떤 집합인지 찾는다.
  서로소 집합은 트리 자료구조를 통해 집합을 표현하고, 연산을 수행한다.
  하나의 트리를 하나의 집합으로 볼 때, find연산은 트리의 루트노드를 찾고, 그 루트노드를 통해 특정 집합을 표현한다.
  그리고, union연산의 경우 두 원소에 대해 find연산을 수행하여 각각의 루트노드를 찾고, 한 쪽의 루트노드를 다른 쪽에 연결함으로써 하나의 트리로 만드는 합집합 연산을 수행한다.

코드

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

public class Main {
	static int n, m;
	static int[] parents;		// 각각의 원소의 부모 노드를 저장하는 배열.  해당 index가 정점이면, 그 value는 부모 node이다.
	
	// 각 사람들을 초기화 해준다.
	// 처음은 다 자기 자신이 부모
	static void make() {
		for(int i = 1; i <= n; i++) {
			parents[i] = i;
		}
	}
	
	static int findSet(int num) {
		// 자신이 root이면 반환
		if(parents[num] == num)
			return num;
		// path compression을 하여 해당 노드를 최상위 노드 바로 밑에 붙게 한다.
		return parents[num] = findSet(parents[num]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b); 
		if(aRoot == bRoot)		// a와 b의 root가 같으면, 같은 집합이므로 종료
			return false;
		parents[bRoot] = aRoot;	// 둘 중 하나를 다른쪽 밑에 붙힌다
		return true;
	}
	
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine()); 
    	
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	parents = new int[n + 1];
    	
    	make();
    	
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		union(stoi(stk.nextToken()), stoi(stk.nextToken()));
    	}
    	
    	int result = 0;
    	
    	for(int i = 1; i <= n; i++) {
    		if(parents[i] == i)		// value가 index와 다르면, root 이므로 종류 갯수를 더 센다
    			result++;
    	}
    	System.out.println(result);
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

★★★★★

후기

없

개선할 점

없