백준 Gold 4 인구 이동

인구 이동 (백준 Gold 4)

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

NxN개의 나라 정보가 주어질때
(각 나라는 1x1 크기)
인구 이동이 며칠 동안 발생하는지를 구하는 문제

조건들

• 이웃나라들끼리 인구비교를 하였을때
  두 인구수의 차이가 L 이상 R 이하인 경우
  ‘국경’을 개방
  

• 모든 나라들에 대하여 위에 대한 조건 판별 후
  국경이 개방된 나라들의 인구수가 평균이 된다
  (국경 개방 나라 인구수 / 국경 개방 나라 수)
  

• 이후 국경을 폐쇄하고
  하루가 지나간다
  

풀이 방법

요점은 '인구 이동의 총 발생 일자'이며
조건이 맞지 않으면 그냥 바로 0일로 끝날수도 있다는 점이다

나는 BFS 탐색 방식을 사용하여 국경 개방 여부를 파악하였다

• 해당 일자에 대한 Visit 배열을 사용하여
  방문 여부 검사
  (조건에 맞지 않으면, 애초에 그나라는 그날 국경 개방이 불가능함)
  

• 두 인접 칸에서 인구수가 l이상 r 이하인지 검사
  
• 동시에 국경을 개방한 나라들의 위치를 저장해둠
  

• 저장한 위치들의 개수가 2개 이상이면 평균을 낸다
  

• BFS가 성공하였다면, 하루가 흘러가고
  아니라면 종료하고 반환
  

제출 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, l, r;

const int dirY[4] = { 0,-1,0,1 };
const int dirX[4] = { -1,0,1,0 };

bool bfs(vector<vector<int>>& maps, vector<vector<bool>>& visit, int y, int x)
{
	if (visit[y][x])
		return false;

	long sumValue = 0;
	vector<pair<int, int>> vecs;
	queue<pair<int, int>> q;

	q.push({ y,x });

	visit[y][x] = true;

	while (q.empty() == false)
	{
		int nowY = q.front().first;
		int nowX = q.front().second;
		q.pop();

		vecs.push_back({ nowY,nowX });
		sumValue += maps[nowY][nowX];

		for (int i = 0; i < 4; i++)
		{
			int ny = nowY + dirY[i];
			int nx = nowX + dirX[i];

			if (ny < 0 || ny >= n ||
				nx < 0 || nx >= n)
				continue;

			if (visit[ny][nx])
				continue;

			int mV = abs(maps[nowY][nowX] - maps[ny][nx]);

			if (mV < l || mV > r)
				continue;

			visit[ny][nx] = true;
			q.push({ ny,nx });
		}
	}

	if (vecs.size() <= 1)
		return false;

	int v = sumValue / vecs.size();
	for (auto& p : vecs)
	{
		maps[p.first][p.second] = v;
	}

	return true;
}

int main()
{
	cin >> n >> l >> r;
	vector<vector<int>> maps(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> maps[i][j];
	int answer = 0;

	while (true)
	{
		bool dayNotChanged = true;

		vector<vector<bool>> visit(n, vector<bool>(n, false));

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (visit[i][j] == false)
				{
					if (bfs(maps, visit, i, j))
					{
						dayNotChanged = false;
					}
				}
			}
		}
		if (dayNotChanged)
			break;

		answer++;
	}

	cout << answer;

	return 0;
}

결과

일반적인 BFS 문제와는 살짝 달라 당황하였지만
문제를 침착하게 보니 풀 수 있었다