[SW7465] 창용 마을 무리의 개수

 SW Expert Academy - 숫자 카드 게임 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=%EC%B0%BD%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 입출력

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

#1 2

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;


public class Solution {
	static int ans, T, N, M;
	static Integer[] parents;
	static Edge[] edges;

	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			// 초기화
			ans = 0;
			parents = new Integer[N + 1];
			edges = new Edge[M];

			makeSet();

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				edges[i] = new Edge(from, to);
			}

			for (Edge e : edges) union(e.f, e.t);

			for (int i = 0; i <= N; i++) findSet(i);

			// 정렬로 변경하여 요소 갯수 구하기
			HashSet<Integer> set = new HashSet<>(Arrays.asList(parents));
			for (int i = 1; i < set.size(); i++) ans++;

			sb.append("#").append(t).append(" ").append(ans).append("\n");

		}

		System.out.println(sb.toString());

	} // end main


	private static void makeSet() {
		for (int i = 0; i <= N; i++) parents[i] = i;
	} // end makeSet


	private static int findSet(int x) {
		if (x == parents[x]) return x;
		return parents[x] = findSet(parents[x]);
	} // end findSet


	private static boolean union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);

		if (px == py) return false;

		if (px < py) parents[py] = px;
		else parents[px] = py;

		return true;
	} // end union


	static class Edge {
		int f;
		int t;


		public Edge(int f, int t) {
			this.f = f;
			this.t = t;
		}


		@Override
		public String toString() {
			return "Edge [f=" + f + ", t=" + t + "]";
		}

	} // end Edge
}

• dfs, bfs 로도 풀 수 있지만 그래프 알고리즘을 이용해서도 풀 수 있다. 
• 서로소로 되어 있는 각각의 노드들을 union() 함수로 묶는다.
• 그렇게 되면 각 노드의 parents 를 알 수 있다. (parents 배열에 저장했기 때문에)
• 해당 parents 의 중복되지 않는 요소의 개수를 세면 된다.

 

 

 

 

 

 

 

 

 

# SW 창용 마을 무리의 개수 java # SWEA 창용 마을 그래프

---