SWExpertAcademy 7465-창용 마을 무리의 개수(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU 

SW Expert Academy

 

창용 마을에는 N명의 사람이 살고 있다.

사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.

두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.

두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,

이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.

창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는

두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.

이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다.

같은 관계는 반복해서 주어지지 않는다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

무리의 개수를 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Solution1 {
	static int N; // 원소갯수
	static int[] parents;// 부모원소 관리
	static int cnt;

	// 모든 원소를 자신의 대표자로 만듦
	private static void make() {
		parents = new int[N+1];
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}

	// a가 속한 집합의 대표자 찾기
	private static int find(int a) {
		if (a == parents[a])
			return a;
		return parents[a] = find(parents[a]);
	}

	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		// 이미 같은 집합이면 union 하지 않음
		if (aRoot == bRoot)
			return false;
		// 같은 집합이 아니라면 합치기
		parents[bRoot] = parents[aRoot];
		return true;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			sb.append("#" + t + " ");
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			//합집합 연산하기 
			make();
			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++) {
				find(i);
			}
			
			//hashset에 대표자를 넣어 중복이 제거된 대표자들의 수 =그룹 수 
			HashSet<Integer> hset = new HashSet<>();
			for (int temp = 1; temp <=N; temp++) {
				hset.add(parents[temp]);
			}
			sb.append(hset.size()+"\n");
		}
		System.out.println(sb);
	}
}

합집합 연산 후 자신이 속한 집합의 진짜 대표자를 찾아 parents를 바꿔준 뒤,

hashset에 parents의 원소 값들을 넣어주면 중복이 제거된 대표자들을 얻을 수 있습니다.

중복이 제거된 대표자들의 수 = 그룹 수 이므로 hset.size를 출력해주었습니다.