[SWEA] D4 7465 창용 마을 무리의 개수 (JAVA)

문제

저작권 문제로 인해 링크만 첨부합니다
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

풀이 방법

서로소 집합에 대해서 공부한 뒤 풀어본 문제였다.  사람 사이의 관계를 입력받아서 총 무리가 몇 개인지 출력하면 된다. 그래서 나는 무리를 합치는 함수와 무리의 대장을 찾는 함수를 따로 선언해줬다.
그리고 입력받은 정보들로 각각의 무리의 대장이 동일하면 그냥 넘어가고 대장이 다르다면 합치는 식으로 구현했다. 
여기서 주의해야할점은 무리의 입력에서 숫자 하나만 올 수도 있다는 점이다. N, M의 범위를 잘봐야한다. 
입력이 1 5 일수도 3 만 올 수도 있다는 의미
이 부분만 주의해주면 어려운 문제는 아니였다. 무리를 전부 업데이트 한 후
이제 중복을 방지하기 위해 boolean배열을 이용해서 무리의 대장이면 카운팅을 해줬다.

 

제출 코드

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

public class D4_7465_창용마을무리의개수 {
	static int[] boss;
	
	private static void union(int a, int b) { //무리 합치기
		boss[findBoss(b)] = findBoss(a);
	}

	private static int findBoss(int a) { //무리의 대장 찾기
		if (boss[a] == a)return a;
		return boss[a] = findBoss(boss[a]);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 1~N번까지의 사람
			int M = Integer.parseInt(st.nextToken()); // 관계 수
			boss = new int[N + 1];
			for (int i = 1; i <= N; i++) {
				boss[i] = i;
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken()); 
				if(st.hasMoreElements()) { //뒤에 두번째 수가 있으면
					int b = Integer.parseInt(st.nextToken());
				if (findBoss(a) != findBoss(b))	//각각의 무리 대장을 찾고 같은 무리인지 확인 
					union(a, b); //아니면 합치기
				}
			}
			boolean[] count = new boolean[N+1]; //무리의 개수를 찾기 위해 cnt했는지 체크할 변수
			int cnt =0; 
			for (int i = 1; i <=N; i++) {
				boss[i] = findBoss(i); //무리의 대장을 업데이트해주고 (예전 대장을 알고 있는 경우가 있음)
				if(!count[boss[i]]) { //만약 체크가 안되어있으면 cnt+1 해주고 체크표시 해주기
					cnt++; 
					count[boss[i]] = true;
				}
			}
			System.out.printf("#%d %d\n", test_case, cnt);
		}
	}
}