[구름톤 챌린지 4주 차 학습 일기] 16일차 미션 문제 16. 연합 (java)

https://level.goorm.io/exam/195698/%EC%97%B0%ED%95%A9/quiz/1

구름LEVEL

---

728x90

 

내 생각

문제 읽자마자 union-find로 풀면 되겠다는 생각이 났다.

근데 알고리즘 문제 성실히 안 푼 지 꽤 돼서 union find 구현하는 방법이 진짜 기억이 안 났다.

오기가 생겨서 찾아보기는 싫고 알고리즘 작동 원리를 떠올리면서 머리 쥐어짜 내서 풀었다.

풀고 보니 코드가 살짝 더러운 거 같아서 마음에 들진 않는다.

---

import java.io.*;
import java.util.*;

class Main {
	
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 섬의 개수 N, 다리의 개수 M 입력
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		parent = new int[N + 1];
		for(int i = 1; i <= N; i++) parent[i] = i;
		
		// s, e 입력
		boolean[][] visited = new boolean[N + 1][N + 1];
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			if(visited[e][s]) { // 양방향 연결이라면
				union(s, e); // 유니온 파인드
			}
			visited[s][e] = true;
		}
		
		// union find로 조상 구하기
		for(int i = 1; i <= N; i++) find(i);
		
		// 연합 개수 세기
		boolean[] visited2 = new boolean[N + 1];
		int result = 0;
		for(int i = 1; i <= N; i++) {
			if(!visited2[parent[i]]) result++;
			visited2[parent[i]] = true;
		}
		
		System.out.println(result);
	}
	
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a == b) return;
		
		if(a <= b) parent[b] = a;
		else parent[a] = b;
	}
	
	private static int find(int a) {
		if(parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}
}