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

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

SW Expert Academy

<문제>

창용 마을에는 N명의 사람이 살고 있다.
사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.
두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.
두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,
이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.
창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

 

<풀이>

그래프를 이용해서 풀면 될 것이라고 생각, 하지만 어떻게 접근해야하는지 생각하는데 어려움이 있었다.

입력이 될때마다 union을 해주고, 최종적으로 root 노드가 자기 자신인 노드 개수를 구하면 된다.

부모 노드를 따라가며 root 노드를 찾을 수 있다. (find) 

	static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		
		if(rootA==rootB) return;
		root[rootA]=rootB;
	}

	static int find(int a) {
		if(root[a]==a) return a;
		else return find(root[a]);
	}

<코드>

package A0303;

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

public class SWEA7465 {
	static int N,M;
	static int[] root;
	
	static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		
		if(rootA==rootB) return;
		root[rootA]=rootB;
	}
	
	static int find(int a) {
		if(root[a]==a) return a;
		else return find(root[a]);
	}
	
	public static void main(String[] args) throws Exception, IOException {
		//System.setIn(new FileInputStream("input_7465.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			root = new int[N+1];
			for(int i=1;i<=N;i++) {
				root[i]=i;
			}
			
			for(int i=0;i<M;i++) {
				st = new StringTokenizer(br.readLine());
				int out = Integer.parseInt(st.nextToken());
				int in = Integer.parseInt(st.nextToken());
				union(out, in);
			}

			int answer =0;
			for(int i=1;i<=N;i++) {
				if(find(i)==i) {
					answer++;
				}
			}
			System.out.println("#"+tc+" "+answer);
		}
	}

}

<느낀점>

root노드만을 이용해서 간단히 풀 수 있는 것이 신기했다. 그래프라면 무조건 어려울 거라는 두려움이 앞섰는데 조금 편하게 접근하는 습관을 들여야겠다.

그래프 union에 대해 알게 되었다. root노드가 자기 자신인 것의 개수를 찾으면 그래프가 몇개로 구성되어있는지 알 수 있다는 것을 알았다.