문제
이해
NxN 2차원 평면에 최초 K개의 문명이 존재한다. 문명은 1년이 지날때마다 인접한 칸으로 전파된다. 문명은 서로 결합될 수 있는데 서로 다른 문명이 인접한 칸에 위치할 때 가능하다.
왼쪽 상단의 그림은 초기의 문명 상태이다. 1년이 지나면 오른쪽 상단처럼 인접한 칸에 문명이 전파되고 2년째에는 서로 맞닿는 문명들이 생긴다. 2년째 그림을 보면 모든 초기 문명이 서로 맞닿아 있어 모두 결합된 상태이다.
2 ≤ N ≤ 2000 이고 2 ≤ K ≤ 100,000일 때 모든 문명이 하나로 결합되는데 걸리는 최소 햇수를 출력해야 한다.
접근
처음에는 문명이 하나로 결합되는데 걸리는 햇수를 구한다는 점에서 각 문명의 최단거리 중 최댓값을 구하는 방향으로 생각해보았다.
무슨 말이냐면 특정 문명이 시간이 지나 가장 먼저 결합되는 다른 문명은 자신과 최단거리에 있는 문명이다. 따라서, 모든 문명이 결합되려면 최단거리가 가장 큰 문명에서의 결합 햇수를 계산하면 된다는 아이디어이다.
하지만, 모든 문명의 최단거리를 구하고 이 중에서 최댓값을 찾아야 하기 때문에 적용할 수 있는 알고리즘은 플로이드 워셜이었다. 플로이드 워셜 알고리즘은 시간복잡도가 N^3이기 때문에 100,000^3임으로 적절하지 않다.
문제를 단순하게 접근하여 Flood Fill 유형처럼 접근했다. BFS를 수행하면서 문명을 계속 전파하는 시뮬레이션을 돌리는 아이디어를 생각해보았다.
공간은 2000x2000이기 때문에 모든 공간을 순회하는 것이 괜찮아보였기 때문이다.
그렇다면 문명을 BFS로 전파하되 어떻게 모든 문명이 결합됨을 알 수 있을까?
최초 문명은 K개로 고정되어 있다. 이는 시뮬레이션이 돌아가면서 서로 결합되는데 이를 위해 서로소 집합을 사용할 수 있다.
BFS를 순회하다가 다음 방문할 노드가 다른 문명이라면? 서로소 집합을 통해 Union 하면 되는 것이다.
전체 알고리즘 구성은 다음과 같다.
- BFS (햇수를 기준으로)
- 방문 후 Union
- n년의 Flood Fill이 끝나면 검사 수행
모든 문명이 결합됐는지는 어떻게 알 수 있을까?
Union-Find의 Find를 사용하면 된다. 문명은 최대 100,000개이기 때문에 햇수마다 문명들의 parents를 검사하는 것은 부적절해보인다. 따라서, 결합될 때마다 count를 추가한다. 결국에는 K개의 문명들이 모두 결합되어야 하기 때문에 시뮬레이션에서 결합되는 경우가 K-1번 발생할 수 밖에 없다. 회차의 BFS가 끝나고 count가 만일 K-1이라면 모든 문명이 결합되었기 때문에 break한다.
시간복잡도
시간복잡도를 확인해보자.
최악의 경우에는 모든 노드를 순회하게 되는데 2000x2000 = 2,000,000으로 충분한 시간으로 보인다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static StringTokenizer st = null;
static int[][] board;
static int[] parents;
static Queue<int[]> q = new ArrayDeque<>();
static int N, K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new int[N + 1][N + 1];
parents = new int[K + 1];
MakeSet();
for (int i = 1; i <= K; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
q.add(new int[] { x, y });
civilSet.add(i);
board[x][y] = i;
}
int ans = bfs();
System.out.println(ans);
}
private static int bfs() {
int depth = 0;
int cnt = 1;
while (true) {
int size = q.size();
while (size-- > 0) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + d[0][i];
int ny = cur[1] + d[1][i];
if (IsOutBound(nx, ny) || board[cur[0]][cur[1]] == board[nx][ny]) {
continue;
}
if (board[nx][ny] != 0) {
if (Union(board[cur[0]][cur[1]], board[nx][ny])) {
cnt++;
}
continue;
}
}
q.add(cur);
}
if (cnt == K) {
break;
}
depth++;
size = q.size();
while (size-- > 0) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + d[0][i];
int ny = cur[1] + d[1][i];
if (IsOutBound(nx, ny) || board[cur[0]][cur[1]] == board[nx][ny]) {
continue;
}
if (board[nx][ny] != 0) {
if (Union(board[cur[0]][cur[1]], board[nx][ny])) {
cnt++;
}
continue;
}
board[nx][ny] = board[cur[0]][cur[1]];
q.add(new int[] { nx, ny });
}
}
if (cnt == K) {
break;
}
}
return depth;
}
private static void PrintForDebug(int depth) {
System.out.println("---------" + depth + "------------");
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
System.out.println();
}
private static void MakeSet() {
for (int i = 1; i <= K; i++) {
parents[i] = i;
}
}
private static int FindSet(int a) {
if (parents[a] == a) {
return a;
}
return parents[a] = FindSet(parents[a]);
}
private static boolean Union(int a, int b) {
int aRoot = FindSet(a);
int bRoot = FindSet(b);
if (aRoot == bRoot) {
return false;
}
parents[bRoot] = aRoot;
return true;
}
private static boolean IsOutBound(int x, int y) {
return x <= 0 || x > N || y <= 0 || y > N;
}
}