[Java] SWEA 7465번 창용 마을 무리의 개수

SW Expert Academy

---

풀이

크루스칼 알고리즘을 사용하여 해결했습니다.

주의할 점은 union만 진행할 경우 최상위 그룹에 속한 부모 값만 바뀌게 되고 하위 그룹에 속한 부모 값은 바뀌지 않게 되므로 findSet을 모든 정점에서 한 번 더 진행하여 하위 그룹의 부모 값도 바뀌게 해주어야 합니다.

---

코드

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

public class Solution {
	public static class Edge {
		int from, to;

		public Edge(int from, int to) {
			super();
			this.from = from;
			this.to = to;
		}
	}
	
	public static int N, M, answer;
	public static boolean[] check;
	public static int[] parents, rank;
	public static List<Edge> edgeList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st = null;		
		
		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());
			
			parents = new int[N + 1];
			rank = new int[N + 1];
			check = new boolean[N + 1];
			edgeList = new ArrayList<Edge>();

			make();
			
			for (int i = 0; i < M; ++i) {
				st = new StringTokenizer(br.readLine(), " ");
				
				union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			
			answer = 0;
			
			for (int i = 1; i <= N; ++i) {
				// union만 할 경우 합쳤을 때 합치기 전의 최상위 부모의 부모값만 바뀌고 그 하위는 바뀌지 않으므로
				// 반드시 findSet을 한번 더 해 path compression을 해주어야 한다.
				int p = findSet(i);
				
				if (!check[p]) {
					check[p] = true;
					answer++;
				}
			}
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static void make() {
		for (int i = 1; i <= N; ++i) {
			parents[i] = i;
		}
	}
	
	public static int findSet(int a) {
		if (parents[a] == a) {
			return a;
		}
		
		return parents[a] = findSet(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if (aRoot == bRoot) {
			return false;
		}
		
		if (rank[aRoot] < rank[bRoot]) {
			parents[aRoot] = bRoot;
		}
		else {
			parents[bRoot] = aRoot;
			
			if (rank[aRoot] == rank[bRoot]) {
				rank[aRoot]++;
			}
		}
		
		return true;
	}
}

---

pyo7410/Algorithm