[백준/BOJ] 백준 14868번 : 문명

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

14868번: 문명

문명별로 번호를 매기고, 인접한 곳과 합쳐질 때 합치는 것과, 찾는 것을 유니온 파인드를 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

vector<vector<int>> board(2001, vector<int>(2001, 0));
int n, k;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int result = 0;
vector<int> parent(100001);
vector<int> rank_size(100001);
queue<pair<int, int>> q;

void Pre()
{
	for (int i = 1; i <= 100000; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
		{
			rank_size[u]++;
		}
	}
}

//문명이 하나로 합쳐졌는지 확인
bool Check()
{
	for (int i = 1; i <= k - 1; i++)
	{
		int u = Find(i);
		int v = Find(i + 1);

		if (u != v)
			return false;
	}

	return true;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> k;

	for (int i = 1; i <= k; i++)
	{
		int x, y;
		int new_x, new_y;

		cin >> x >> y;

		//왼쪽위를 (1,1)로 하는 좌표로 만든다
		new_x = (n + 1) - y;
		new_y = x;

		pair<int, int> here = make_pair(new_x, new_y);
		board[here.first][here.second] = i; //문명의 번호를 체크한다

		q.push(here);

		//인접한 곳을 확인하여 합쳐지는 문명이 있는지 확인한다
		for (int j = 0; j < 4; j++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[j][0], here.second + dxdy[j][1]);

			if (there.first >= 1 && there.first <= n && there.second >= 1 && there.second <= n)
			{
				if (board[there.first][there.second] != 0)
				{
					int u = i;
					int v = board[there.first][there.second];

					if (Find(u) != Find(v))
					{
						Merge(u, v);
					}
				}
			}

		}
	}

	while (1)
	{
		//문명이 하나로 합쳐졌는지 확인
		if (Check())
			break;

		result++;

		int q_size = q.size();

		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> here = q.front();
			int here_number = board[here.first][here.second];
			q.pop();

			for (int j = 0; j < 4; j++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[j][0], here.second + dxdy[j][1]);

				if (there.first >= 1 && there.first <= n && there.second >= 1 && there.second <= n)
				{
					if (board[there.first][there.second] != 0)
					{
						int u = board[here.first][here.second];
						int v = board[there.first][there.second];

						if (Find(u) != Find(v))
						{
							Merge(u, v);
						}
					}

					else
					{
						board[there.first][there.second] = here_number;
						q.push(there);

						for (int k = 0; k < 4; k++)
						{
							pair<int, int> there_there = make_pair(there.first + dxdy[k][0], there.second + dxdy[k][1]);

							if (there_there.first >= 1 && there_there.first <= n && there_there.second >= 1 && there_there.second <= n && board[there_there.first][there_there.second] != 0)
							{
								if (Find(board[there.first][there.second]) != Find(board[there_there.first][there_there.second]))
								{
									Merge(board[there.first][there.second], board[there_there.first][there_there.second]);
								}
							}
						}

					}
				}
			}
		}
	}

	cout << result;

	return 0;
}