[JAVA]SWEA_7465_창용마을무리의개수

문제링크

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

 

 

 

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

public class Solution {

	static int N,M;
	static int parents[];
	static boolean isVisited[];
	static int cnt;

	static void make() {
		for(int i=1;i<N+1;i++) parents[i] = i;
	}
	
	static int findSet(int a) {
		if(parents[a] == a) return a;
		
		return parents[a] = findSet(parents[a]);
	}
	
	static boolean union(int a,int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot) return false;
		
		if(aRoot< bRoot) { 
			parents[bRoot] =aRoot;
			for(int i=1;i<N+1;i++) {
				if(parents[i] == bRoot) parents[i] = aRoot;
			}
		}
		else {
			parents[aRoot] = bRoot;
			for(int i=1;i<N+1;i++) {
				if(parents[i] == aRoot) parents[i] = bRoot;
			}
		}
		
		return true;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=0;t<T;t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			parents = new int[N + 1];
			isVisited = new boolean[N + 1];
			cnt = 0;

			make();

			//System.out.println(Arrays.toString(parents));
			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);
			}
			
			//System.out.println(Arrays.toString(parents));
			for (int i = 1; i < N + 1; i++)
				isVisited[parents[i]] = true;

			for (int i = 1; i < N + 1; i++) {
				if (isVisited[i])
					cnt++;
			}

			System.out.println("#" + (t + 1) + " " + cnt);
		}

	}
}

 

배열을 사용해서 마을 사람들의 관계를 나타내 주었다.

Union을 사용했다.

 

만약 서로 연결이 있으면 root를 바꾸어 줌으로써 연관관계를 나타내었다.

1-3

2-3

이면 1-2-3이 연결관계가 있고

4-5

5-6

이면 4-5-6으로 연결관계가 있어 배열에는

1	2	3	4	5	6
1	1	1	4	4	4

이렇게 값이 들어가 있는 상태이다.

 

만약 여기서 1-4를 추가해주면

모두 연관관계가 되어서 모두 1값으로 바꾸어주어야한다.

 

그래서 Union 부분에서 

for문을 돌려 원래 4의 자식들이었던 놈들을 다 1의 자식으로 바꾸어주는 과정을 거쳤다.