[백준/BOJ] 백준 16234번 : 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

국경이 열리는 나라들을 확인할 때 bfs를 통해 확인하고, 국경이 열려서 만들어지는 연합의 지점들을 저장해 놓고 각 연합의 인구수를 재설정한다.

 

코드

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

int n, l, r;
int board[50][50];
int discovered[50][50];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<vector<pair<int, int>>> change;
bool changed;

void Pre()
{
	changed = false;

	for (int i = 0; i < change.size(); i++)
		change[i].clear();

	change.clear();

	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			discovered[i][j] = 0;
}

void Bfs(pair<int, int> start)
{
	discovered[start.first][start.second] = 1;

	queue<pair<int, int>> q;
	q.push(start);

	vector<pair<int, int>> this_change;

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//이번 영역에 바뀌는 지점들 저장
		this_change.push_back(here);

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

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discovered[there.first][there.second] == 0)
			{
				//인구 차이가 l명 이상 r명 이하일때
				if (abs(board[here.first][here.second] - board[there.first][there.second]) >= l && abs(board[here.first][here.second] - board[there.first][there.second]) <= r)
				{
					discovered[there.first][there.second] = 1;
					q.push(there);

					changed = true;
				}
			}
		}
	}

	change.push_back(this_change);
}

int Solve()
{
	int ret = 0;

	while (1)
	{
		Pre();

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				//탐색하지 않은 부분일때
				if (discovered[i][j] == 0)
				{
					Bfs(make_pair(i, j));
				}
			}
		}

		//인구 이동이 더 이상 없을때
		if (changed == false)
			break;

		//인구 이동하는 칸의 인구수를 재설정한다
		else
		{
			for (int i = 0; i < change.size(); i++)
			{
				int sum = 0;

				for (int j = 0; j < change[i].size(); j++)
				{
					sum += board[change[i][j].first][change[i][j].second];
				}

				for (int j = 0; j < change[i].size(); j++)
				{
					board[change[i][j].first][change[i][j].second] = sum / change[i].size();
				}
			}

			ret++;
		}
	}

	return ret;
}

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

	cin >> n >> l >> r;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int input;

			cin >> input;
			board[i][j] = input;
		}

	cout << Solve();

	return 0;
}