(Java/자바) - SWEA 7465번 : 창용 마을 무리의 개수

 

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

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

 

---

• 풀이 :

창용 마을의 무리 즉, 그래프가 총 몇 개 존재하는지 찾는 문제였습니다.

 

연결관계를 생성한 후 BFS나 DFS를 통해 탐색하여 카운트하는 방법을 사용할 수도 있고 집합의 union 연산을 통해 그래프를 생성하여 root인 노드의 개수를 세는 방법이 있는데 저는 후자의 방법을 사용했습니다.

 

 

1.  root의 번호를 저장한 graph 배열 선언. 이 때, 입력받은 번호를 바로 사용하기 위해 N+1만큼 선언

 

2. 1~N까지의 i에 대해 graph[i] = i 로 초기화, 처음에 자신의 루트노드는 무조건 자기 자신이다.

 

3. M번 입력을 받으면 a와 b를 union한다. 

 

union 방법 -> B의 root 노드를 A와 같게 만들어준다.

 

4. 모든 입력을 받은 후 여전히 graph[i] == i 인 개수가 집합의 개수이다. 0은 사용하지 않지만 매번 카운트되므로 answer를 -1부터 시작하도록 하였다.

 

 

 

---

• 소스코드 : 

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

public class Solution{
	static int TC, N, M, a, b, answer;
	static int[] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			graph = new int[N+1];
			answer = -1; // 0번째 노드는 사용하지 않는데 항상 카운트되므로 answer은 -1부터 시작
            
                    // 초기에 자기 자신의 parent는 자신이다.
			for (int i = 0; i < N+1; i++) {
				graph[i] = i;
			}
            
                    // 입력을 받으며 두 node를 union한다.
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				union(a,b);
			}
            
                    // union 한 이후에 root의 개수, 즉 parent[i] = i인 것들의 개수가 집합의 개수이다.
			for (int i = 0; i < N+1; i++) {
				if(graph[i] == i) answer ++;
			}
			sb.append("#").append(testCase).append(" ").append(answer).append("\n");
		}
		System.out.println(sb.toString());
	}
	private static void union(int a2, int b2) {
    
                // a와 b의 root를 찾는다.
		int aRoot = find(a2);
		int bRoot = find(b2);
  
                // 두 집합의 root를 같게 만들어줌
		graph[bRoot] = aRoot;
	}
	
	private static int find(int a2) {
    	//a2가 루트노드일 경우 a2 리턴
		if(graph[a2] == a2) return a2;
        
        // 아닐경우 a2의 루트의 루트노드를 찾아서 반환
		return find(graph[a2]);
	}

}