BOJ - 14868 ) 문명

개발자가될수있을까? 2020. 4. 18. 16:27

https://www.acmicpc.net/problem/14868

14868번: 문명

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x,y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x,y ≤N)

www.acmicpc.net

문명을 bfs로 전파하면서 전체 문명의수가 한개가되는 즉, union-find를 동시에 수행하면서

전체 root가 1개가 되는 시점을 찾으면된다.

편향트리가 될수있기에, rank를 이용하여서 꼭 정리를 해주어야한다.

이러한 disjoint set과 완전탐색이 결합된 문제를 자주 풀어야겠다..

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


public class 문명{
	
	public static int find(int x) {
		if(p[x] == x)return x;
		return find(p[x]);
	}
	public static boolean union(int x1 , int x2) {
		x1 = find(x1);
		x2 = find(x2);
		if(x1==x2) return false;
		else {
			if(rank[x1] > rank[x2]) {
				p[x2] = x1;
			} else if(rank[x1] < rank[x2]) {
				p[x1] = x2;
			} else {
				rank[x1]++;
				p[x2] = x1;
			}
		}
		return true;
	}
	public static int p[], rank[];
	public static int map[][];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		p = new int[k+1];
		rank = new int[k+1];
		ArrayDeque<int[]> dq = new ArrayDeque<>();
		ArrayDeque<int[]> ddq = new ArrayDeque<>();
		int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		map = new int[n][n];
		for(int i = 1 ; i <= k ; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			map[y][x] = i;
			p[i] = i;
			dq.add(new int[] {y,x});
		}
		
		//System.out.println(Arrays.toString(p));
		
		int year = 0;
		while(true) {
			while(!dq.isEmpty()) {
				int now[] = dq.poll();
				ddq.add(new int[] {now[0], now[1]});
				int y = now[0] , x = now[1];
				
				for(int i = 0 ; i < 4 ; i++) {
					int ny  = y + dir[i][0];
					int nx  = x + dir[i][1];
					if(ny >= 0 && nx >= 0 && nx < n && ny < n) {
						if(map[ny][nx] != 0) {
							if(map[ny][nx] != map[y][x]) {
								if(union(map[ny][nx], map[y][x])) { 
									k--;
								}
							}
						}
					}
				}
			}
			if(k==1) {
				System.out.println(year); break;
			}
			
			while(!ddq.isEmpty()) {
				int now[] = ddq.poll();
				int y = now[0] , x = now[1];
				for(int i = 0 ; i < 4 ; i++) {
					int ny = y + dir[i][0];
					int nx = x + dir[i][1];
					if(ny >= 0 && nx >= 0 && nx < n && ny < n) {
						if(map[ny][nx] == 0) {
							map[ny][nx] = map[y][x]; //그냥 문명 전파
							dq.add(new int[] {ny,nx});
						}
						else if(map[ny][nx] != 0 && map[ny][nx] !=map[y][x]) {
							if(union(map[ny][nx], map[y][x])) { 
								k--;
							}
						}
					}
				}
			}year++;
		}
	}
}