백준 14868: 문명

문제 요약

세계를 N × N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 형태로 생각할 수 있다. 가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N) 위치에 있다.

한 해가 지날 때마다 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.

세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• BFS
• 분리 집합

문제 풀이

각 문명 발생지를 각각의 집합으로 분리하고, 각 집합의 영역을 점자 넓혀나가며 다른 문명과의 연결성을 구하는 문제이다. 이때 어떠한 집합의 크기와 방문한 칸의 개수가 같다면 모든 문명이 연결된 상태로 본다. 이를 BFS로 탐색하며 최소값을 구하면 된다.

우선 문명발생지와 그렇지 않은 미개척지를 구분할 필요가 있었다. 따라서 초기에 모든 미개척지는 유니온의 루트를 0번 칸으로 두었다. 여기서 p[0]을 음수로 둘 필요가 있으며, 즉, find(n)이 0이라면, n번 칸은 미개척지라는 뜻이다. 모든 미개척지는 0번 집합에 속해있다고 볼 수 있으며, 어떠한 문명지역이 입력될 때, 해당 칸을 루트로 새로운 집합을 만든다. 이를 위해서 0번칸은 미개척지를 위해 남겨두었으며, 행과 열의 넘버링은 1부터 시작하여, i행 j열의 경우 (i-1)*n+j의 고유한 값을 가지도록 했다.

nearyby()를 사용하여 주변 문명의 인접 여부를 탐색하였다. 이것은 다른 새로운 노드를 방문하는 용도가 아닌, 인접한 다른 문명과의 병합을 위한 것이다. 즉 find(nt)가 0이 아닐 때 그곳이 어떠한 문명지임을 알 수 있으며, 그곳과 병합하는 연산을 해주었다. 이 함수는 초기 문명 발생지가 입력받을 때와, 문명을 개척하였을 때, 두가지 경우에 모두 호출해 주었다.

초기에 문명지의 위치 번호((i-1)*n+j)를 모두 큐에 넣고, 인접 문명들을 병합한 뒤에 bfs를 실시한다. 여기서 이미 모든 문명이 연결된 상태라면 탐색을 종료한다. 그 후 큐의 값을 받아와서, 상하좌우의 미개척지를 자신의 문명으로 삼는다. 미개척지는 모두 0번 집합에 속하므로 함부로 병합해서는 안되고, 그 칸의 부모를 자신이 속한 집합의 루트로 삼고, 그 집합의 크기를 1 늘려주었다. 즉, 기존 0번 집합과의 연결을 끊고, 자신의 집합으로 연결해주었다. 또한 새로운 칸을 방문했으므로 카운트 해준다. 미개척지를 문명화 한 칸으로부터 상하좌우, 인접한 문명을 탐색하여 병합하는 nearby()도 호출하여 병합해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int p[4000001], n;

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

void nearby(int x, int y, int t) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		int nt = (nx - 1) * n + ny;
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
			if (find(nt) != 0)
				merge(t, nt);
		}
	}
}

int main()
{
	int k, x, y, level = 0, qsize, pos = -1, cnt = 0;

	queue<int> q;
	scanf("%d %d", &n, &k);
	p[0] = -1;
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &x, &y);
		x--;
		q.push(x * n + y);
		if (pos == -1)
			pos = x * n + y;

		p[x * n + y] = -1;
		nearby(x + 1, y, x * n + y);
	}
	cnt = k;
	while (!q.empty()) {
		if (p[find(pos)] == -cnt) break;
		level++;
		qsize = q.size();
		while (qsize--) {
			int t = q.front();
			int cx = (t - 1) / n + 1, cy = (t - 1) % n + 1;
			for (int i = 0; i < 4; i++) {
				int nx = cx + dir[i][0];
				int ny = cy + dir[i][1];
				int nt = (nx - 1) * n + ny;
				if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
					if (find(t) == find(nt)) continue;
					else if(find(nt) == 0) {
						p[find(t)]--;
						p[nt] = find(t);
						cnt++;
					}
					nearby(nx, ny, nt);
					q.push(nt);
				}
			}
			q.pop();
		}
	}
	cout << level;
}