[알고리즘] 7465. 창용 마을 무리의 개수

0. 문제

 

SW Expert Academy

 

[알고리즘] 창용 마을 무리의 개수

c++로 푼 적 있는 문제다.

 

java로 다시 풀어보고, Union-Find로도 풀어보았다.

 

---

1. 문제 이해

 

1. 인접리스트의 완전탐색
2. 서로소 집합 (Union-Find)

 

---

2. 제출

가. DFS

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

public class SWEA7465 {

	static int N, M, ret;
	static List<Integer>[] g; // 인접 리스트
	static boolean[] vis;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuffer sb = new StringBuffer();

		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ret = 0;
			vis = new boolean[N+1]; // 1 ~ N

			// 인접리스트 초기화
			g = new List[N+1];
			for(int i=0; i<=N; i++) {
				g[i] = new ArrayList<Integer>();
			}
			int x, y;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				g[x].add(y);
				g[y].add(x);
			}
			

			for(int i=1; i<=N; i++) { // 1 ~ N
				if(vis[i]) continue;
				dfs(i);
				ret++;
			}
			
			sb.append("#").append(tc).append(" ").append(ret).append("\\n");
		}
		System.out.println(sb);
		br.close();
	}
	
	private static void dfs(int idx) {
		vis[idx] = true;
		
		for(Integer next : g[idx]) {
			if(vis[next]) continue;
			dfs(next);
		}
	}

}

 

---

나. Union-Find

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

// Union-Find로 풀기
public class BOJ7465_2 {

	static int N, M, ret;
	static int[] p; // 부모 노드를 저장
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuffer sb = new StringBuffer();
		
		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ret = 0;
			p = new int[N+1];
			
			make();

			int x, y;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				union(x,y);
			}
			for(int i=1; i<=N; i++) { // 서로소 집합의 수를 센다.
				if(find(i)==i) ret++;
			}
			
			sb.append("#").append(tc).append(" ").append(ret).append("\\n");
		}
		
		System.out.println(sb);
		br.close();
	}
	
	private static void make() {
		for(int i=1; i<=N; i++) {
			p[i] = i;
		}
	}
	
	private static int find(int x) {
		return (x == p[x]) ? x : (p[x] = find(p[x]));
	}

	private static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		p[y] = x;
	}

}

 

---