백준 14868번 문명 문제 해설, BFS 와 Union-Find 알고리즘 을 사용하여 해결하기

백준 14868번 문명 문제 해설

solved.ac 기준 플레티넘 4 난이도의 문제입니다. 기본적으로 BFS 를 사용하여 문제 풀이에 접근할 수 있지만 입력 행렬의 row, col 크기가 매우 커서 (무려 2000칸 !) 이 부분을 어떻게 해결할 것 인가 가 문제의 핵심 이였습니다.

이 문제를 해결하기 위해선 최소 비용 신장 트리에서 사용된 Union-Find 알고리즘 에 대한 이해가 필요합니다.

보통 자료구조 수업에서 배우거나 그래프 문제들을 풀다보면 자연스럽게 한번은 보게되는 내용이며 그렇게 어렵지 않은 내용이므로 한번씩 다시 복습해보고 오시는것을 추천드립니다!

문제부터 살펴보겠습니다.

문제

인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다. 
여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.

세계를 N×N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 
형태로 생각할 수 있다. 가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N) 위치에 있다. 
두 정사각형 (a,b)와 (a′,b′)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.

|a-a′| = 1 이고 b = b′.
|b-b′| = 1 이고 a = a′.

문명의 최초 발상지는 모두 서로 다른 K곳에 있다. 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다. 
문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다. 
한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 정사각형 (a,b)가 문명 지역이면, 
다음 해에는 세계의 경계를 넘지 않는 한 이 정사각형과 인접한 네 정사각형 (a+1,b), (a-1,b), (a,b+1), (a,b-1)
에 문명이 전파된다. 만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 
전파된다면 이 문명들은 결합된다.

예를 들어, 다음과 같이 5×5 크기의 세계에 4곳의 정사각형 (1,1), (2,1), (2,5), (5,2)가 
문명의 발상지라고 하자. 정사각형 (1,1), (2,1)의 문명은 인접해 있으므로 처음부터 결합되어 있다. 
1년후 문명이 전파된 지역은 오른쪽 그림과 같고, 2년 후에 문명이 전파된 지역은 아래 그림과 같다. 
이때 모든 문명은 서로 결합되어 하나의 문명이 된다. 
(2,5)에서 발상한 문명과 (5,2)에서 발상한 문명은 직접적으로 결합되지는 않았지만, 
(1,1),(2,1)에서 발상한 문명을 통하여 결합됨에 주의하라.

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

입력

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

출력

표준 출력으로 모든 문명이 하나로 결합되는데 걸리는 최소 햇수를 정수로 출력한다.

예제입력

예제출력

문제 풀이

기본적으로 2차원 배열에서 문명들이 상, 하, 좌, 우 인접한 칸 으로 매번 전파된다는 조건이므로, 쉽게 BFS 로 문제 풀이를 먼저 접근해볼 수 있습니다.

문명이 어떻게 주어진 조건에 따라 결합되고, 전파되는지 그 과정을 그림으로 살펴보겠습니다.

그림1 우선 문제에서 예시로 든 상황을 살펴 보겠습니다. 위의 그림과 같이 초기 문명이 배치된 상황입니다.

각각의 문명을 구분하기 위해, 번호를 매겨서 표현하였습니다.

그림2 문명이 배치가 되어있을때, 가장 먼저 취할수 있는 행동은 인접한 문명의 결합 입니다.

문제의 종료 조건이 모든 문명이 결합 된 경우 이므로, 가장 먼저 결합할 수 있는 문명들은 결합해준 후 결합되지 않은 문명의 갯수가 몇 개 인지를 따져봐야겠죠!

인접한 경우 의 정의를 상, 하, 좌, 우 로 문명이 배치되어 있는 경우 로 문제에서 정의하였으므로, 위의 그림과 같은 문명 배치 에서는 문명 1, 문명 2 가 서로 결합 될 수 있네요.

그림3 인접한 문명들을 결합한 후에 취할수 있는 행동은 바로 문명을 주위의 인접한 칸 들로 전파하는 것 이죠.

문제의 조건에 따라 인접한 칸 인 상, 하, 좌, 우 칸 들로 문명을 전파해 줍니다. 이때 그림만 봐도 BFS 를 사용하여 이 부분은 쉽게 구현할 수 있을것 같네요

여기까지만 살펴보면 굉장히 쉬운것 같네요! 하지만 한가지 문제점이 있습니다.

바로 문명이 위치하는 세계의 크기가 최대 2000 x 2000 이라는 점 이죠!

BFS 는 세계의 모든 칸을 채워 나가므로 시간복잡도가 O(N ^ 2) 이라는 것을 알 수 있습니다. N = 2000 일 때에는 제한시간 안에 충분히 해결이 가능합니다.

하지만, 문명을 결합할 때에 문제가 발생합니다.

문명을 위의 그림처럼, 인접한 문명의 값들을 모두 같은 값으로 직접 바꿔줘야 한다면, 이때 결합을 실행하는 시간 복잡도 또한 O(N ^ 2) 에 근접할 것 이라는 것을 알 수 있습니다.

문명을 전파하는 과정이 O(N ^ 2) 이며 전파 단계마다 결합할 수 있는 문명을 확인후에 결합한다면, 결합에 드는 시간복잡도도 O(N ^ 2) 이므로 전체 시간복잡도가 O(N ^ 4) 에 근접하게 되어 시간초과가 날 수 밖에 없겠죠. 물론 최악의 상황이긴 하지만요!

따라서, 문명을 결합하는 방법 부분에서 조금 더 빠른 방법을 사용하여 해결해야 한 다는 것 을 알 수 있습니다.

어떤 방법으로 최적화가 가능한지 알아보겠습니다.

문명을 빠르게 결합하는 방법

그림4 인접한 문명을 결합할 수 있는 상황입니다.

이때 가장 간단한 구현 방법은, 인접한 문명들의 번호를 같은 번호로 만들기 위해 직접 2차원 배열에 접근하여 각각의 문명에 속해있는 칸들의 x, y 좌표에 해당하는 값을 바꿔주는 방법이 있습니다. 문명에 속한 칸들의 좌표는 BFS 방법을 다시한번 사용해서 같은 번호를 가진 칸들을 얻어내면서, 그 칸들의 값을 바꿔줄 수 있겟죠.

하지만, 앞서 살펴봤듯이 이러한 방식으로 구현하게 되면 2000 x 2000 이나 되는 큰 배열에서 제한시간 안에 문제를 해결할 수 없습니다.

이러한 상황에서 쓰기 적합한 알고리즘이 바로 Union-Find 알고리즘 입니다.

직접 문명에 속한 칸들의 번호를 바꾸는게 아닌, 각각의 문명이 어떤 문명에 속해있는지 정보만 유지하는 방법이죠!

예를들어, 최초의 문명 배치 상황에서는 결합이 한 번도 이루어지지 않았으므로 1번 문명은 1번문명에 속해있고, 2번 문명은 2번 문명에, … , N번 문명은 N 번 문명에 속해 있습니다.

이때 위의 그림같이 1, 2번 문명을 결합한다고 하면, 2번 문명이 속한 문명의 값을 2번 에서 1번으로 바꿔주는 것 이죠.

이런식으로 접근한다면, 문명을 결합할 때 각 문명에 어디에 속해있는지 딱 1번만 갱신해주면 되므로, 시간 제한 안에 충분히 해결이 가능합니다.

문명을 결합하고, 전파하는 과정

이제 문명을 빠르게 결합하는 방법을 알았으니, 문명을 어떨 때 결합해야 하고 어느 조건에서 전파해야 하는지 하나하나 따져보겠습니다.

우선, 문명은 상, 하, 좌, 우 로 퍼져가므로 각각의 문명에 속한 모든 칸을 가지고 있을 필요가 없습니다.

가장 최근에 전파되었던, 문명의 최 외곽에 있는 칸 들만 큐에 넣어둔다면 그 칸들만 다음에 또 인접한 칸 들로 전파하면 되겠죠!

문명을 인접한 칸에 전파하는 조건은 생각해보면 다음과 같습니다.

인접한 칸에 문명이 존재하지 않는다

상, 하, 좌, 우 로 인접한 칸에 이미 다른 문명이 존재한다면, 이미 전파하기 전 결합 단계에서 하나의 같은 문명으로 결합되었을 테니 또 같은 문명에다가 전파할 필요는 없겠죠.

문명을 결합하는 조건은 생각해보면 다음과 같이 정리할 수 있습니다.

인접한 칸에 문명이 존재하며, 현재 칸의 문명과 다른 문명이다

결합하는 조건도 쉽게 도출해 낼 수 있습니다. 문명이 결합되려면 우선 인접한 칸에 문명이 존재해야 하며, 이떄의 인접한 문명은 다른 번호의 문명이어야 됩니다.

여기까지 도출해낸 방법들 만 있으면 문제를 충분히 해결할 수 있을 것 같네요.

바로 소스코드로 옮겨보겠습니다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
#include <list>
#include <cassert>

using namespace std;

int row, col;
int num;

int map[2001][2001];
int parent[100001];	// 문명이 어떤 문명에 포함되어 있는지를 나타내는 배열

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

queue<pair<int, int>> union_q;
queue<pair<int, int>> bfs_q;

// Union-Find 알고리즘, 현재 문명이 어떤 문명에 속해 있는지를 반환
int find_parent(int idx)
{
	if (idx == parent[idx])
		return idx;

	else
		return parent[idx] = find_parent(parent[idx]);
}

// 두 문명이 각각 다른 문명에 속해있다면 두 문명을 결합
void merge(int a, int b)
{
	int parentA = find_parent(a);
	int parentB = find_parent(b);

	if (parentA != parentB)
	{
		parent[parentA] = parentB;
	}
}

// 두 문명이 같은 문명에 속해있는지 반환
bool is_same_parent(int a, int b)
{
	int parentA = find_parent(a);
	int parentB = find_parent(b);

	return parentA == parentB;
}

// 인접한 문명을 결합
void merge_civil()
{
	while (union_q.empty() == false)
	{
		int curx = union_q.front().first;
		int cury = union_q.front().second;
		bfs_q.push({ curx, cury });
		union_q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = curx + dx[i];
			int ny = cury + dy[i];
			int cur_civil = map[curx][cury];
			int neighbor_civil = map[nx][ny];

			if (nx < 0 || nx >= row || ny < 0 || ny >= col || map[nx][ny] == 0)
				continue;

            // 인접한 문명이 다른 번호이며 다른 문명에 속해있어야만 결합한다
			if (cur_civil == neighbor_civil || is_same_parent(cur_civil, neighbor_civil))
				continue;

			merge(cur_civil, neighbor_civil);
            // 두 문명이 하나의 문명으로 결합되었으므로, 전체 문명의 수를 하나 낮춘다
			num--;
		}
	}
}

// 문명을 인접한 칸에 전파
void bfs_civil()
{
	while (bfs_q.empty() == false)
	{
		int curx = bfs_q.front().first;
		int cury = bfs_q.front().second;
		bfs_q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = curx + dx[i];
			int ny = cury + dy[i];

			if (nx < 0 || nx >= row || ny < 0 || ny >= col || map[nx][ny] != 0)
				continue;

            // 인접한 칸에 문명이 존재하지 않는 경우
			map[nx][ny] = map[curx][cury];
			union_q.push({ nx, ny });

		}
	}
}
	
void solve()
{
	int count = 0;

	while (num > 1)
	{
		merge_civil();

		if (num == 1)
		{
			cout << count << endl;
			return;
		}

		bfs_civil();

		count++;
	}
}

int main()
{
	cin >> row >> num;
	col = row;

	for (int i = 0; i < num; i++)
	{
		int x, y;	cin >> x >> y;
		union_q.push(make_pair(x - 1, y - 1));
		map[x - 1][y - 1] = i + 1;
	}

	for (int i = 0; i < 100001; i++)
		parent[i] = i;

	solve();

	return 0;
}

문제의 접근방식과 아이디어를 그대로 소스코드로 구현하였습니다.

문명을 결합하는 과정에서 Union-Find 알고리즘에서 사용된 아이디어를 그대로 가져와서 구현하였습니다.

채점결과

문제풀이 후기

이 문제는 기본적으로 BFS 로 접근해야 한다는 것은 쉽게 알수 있었지만, 문명들의 포함 정보를 어떻게 빠르게 갱신할 수 있을까 를 생각해 낼 수 있는지 에 대한 문제였습니다.

처음에 접근했을 때 에는 문명의 번호를 문명에 속해있는 칸 마다 각각 바꿔주는 방식으로 생각해서 당연히 시간초과가 날 수 밖에 없었네요.

Union-Find 알고리즘은 이러한 집합의 원소의 포함관계 판단 이외에도 최소 비용 신장 트리 생성에도 유용하게 쓰이므로 알아두는 것이 좋습니다. 다양한 방면에서 활용이 가능하죠.

코드의 구현 또한 간단한 편에 속하므로, 이참에 복습하고 넘어가는게 좋겠네요!

감사합니다.