[BOJ / 유니온파인드 BFS] 14868 문명

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

14868번: 문명

14868 문명

알고리즘 : 유니온파인드/BFS/메모이제이션

KOI 2017 2번문제입니다. 유니온 파인드를 이용하여 각 문명의 부모를 빠른 시간안에 가져오도록 하고,  간선의 가중치가 1인 상황에서 BFS를 이용하면 현재 상태에서 최단해가 나오는 성질을 이용하여 문제를 풀이하였습니다. 초기값에서 답이 나오는지 체크를 하고

중간중간에 특이 문명을 연결해주는 경우를 해주어야 예외가 나오지 않습니다. 메모이제이션과 유니온파인드를 이용하여 시간단축을 해주어야 시간초과가 나오지 않습니다.

 

 

 

< CODE >

#include <iostream>
#include <queue>

using namespace std;

#define MAX 2005

struct forQ
{
	int first;
	int second;
	int year;
};

pair<int, int> par[MAX][MAX];
int Rank[MAX][MAX];
int childNum[MAX][MAX];
int years[MAX][MAX];
bool chk[MAX][MAX];
queue<forQ> q;
int firstDay = 1;

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

int allGround = 0;
pair<int, int> zero = { 0,0 };
int answer = 987654321;
int now = 0;


bool safe(int y, int x)
{
	if (y == 0 || x == 0 || y == n + 1 || x == n + 1)
		return false;
	return true;
}

pair<int, int> _find(pair<int, int> p)
{
	if (p == par[p.first][p.second])
		return p;

	return par[p.first][p.second] = _find(par[p.first][p.second]);
}

void _union(pair<int, int> p, pair<int, int> c)
{
	int mYear = max(years[p.first][p.second], years[c.first][c.second]);

	p = _find(p);
	c = _find(c);

	if (p == c)
		return;

	if (Rank[p.first][p.second] < Rank[c.first][c.second])
	{
		par[p.first][p.second] = par[c.first][c.second];
		childNum[c.first][c.second] += childNum[p.first][p.second];

		if (childNum[c.first][c.second] == allGround)
			answer = min(answer, mYear);
	}
	else
	{
		par[c.first][c.second] = par[p.first][p.second];
		childNum[p.first][p.second] += childNum[c.first][c.second];

		if (childNum[p.first][p.second] == allGround)
			answer = min(answer, mYear);
	}

	if (Rank[p.first][p.second] == Rank[c.first][c.second])
		Rank[p.first][p.second]++;
}

void myCheck(pair<int, int> p)
{
	for (int j = 0; j < 4; j++)
	{
		pair<int, int> aCh = { p.first + dy[j], p.second + dx[j] };

		if (safe(aCh.first, aCh.second) && chk[aCh.first][aCh.second] && _find(p) != _find(aCh))
		{
			_union(p, aCh);
			myCheck(aCh);
		}
	}
}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			Rank[i][j] = 1;
			childNum[i][j] = 1;
			par[i][j] = make_pair(i, j);
			years[i][j] = -1;
		}
	}

	for (int i = 0; i < m; i++)
	{
		pair<int, int> s;

		cin >> s.first >> s.second;

		chk[s.first][s.second] = true;
		years[s.first][s.second] = 0;
		q.push({ s.first, s.second ,0 });

		myCheck(s);
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			firstDay = max(firstDay, childNum[i][j]);

	allGround = m;

	if (m == 1 || allGround == firstDay)
	{
		cout << "0\n";
		return 0;
	}

	while (!q.empty())
	{
		forQ cur = q.front(); q.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> to = { cur.first + dy[i], cur.second + dx[i] };

			if (safe(to.first, to.second))
			{
				if (!chk[to.first][to.second])
				{
					chk[to.first][to.second] = true;
					allGround++;
					years[to.first][to.second] = cur.year + 1;
					q.push({ to.first, to.second, cur.year + 1 });

					myCheck(to);
				}

				_union(make_pair(cur.first, cur.second), to);
			}
		}
	}

	cout << answer << '\n';

	return 0;
}

시간 : 1500ms

 

태그 : #BOJ 문명 #백준 문명 #14868 문명 #문명 풀이 #KOI 2017 문명