[BOJ / 삼성A형기출] 16234 인구 이동

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

16234번: 인구 이동

 

16234 인구이동

 

알고리즘 : BFS, 시뮬레이션

floodfill 방식의 문제로 시뮬레이션 느낌이 나는 bfs 문제입니다. 중복 처리와 나라별 배분법을 잘 생각해보면

간단하게 풀이할 수 있습니다. 처리되지 않은 나라에서 bfs를 돌려 닿을 수 있는 모든 나라를 체크해 보관하고 일괄 처리 해주면 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

#define MAX 55

// 인구수
int popu[MAX][MAX];

// 어떤 나라와 연합했는지
int condi[MAX][MAX];

// 나라 번호
int cnt = 1;

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

// 나라별 병합수와 총 합
// 모든 나라가 인구수가 똑같을 경우 n*n개의 개별국으로 나뉘므로 
pair<int, int> sum[MAX*MAX];

bool loop = true;

int n, l, r;
int result = 0;

// 각 단계별 초기화
void clear()
{
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			condi[i][j] = 0;

	for(int i = 0; i < MAX*MAX; i++)
		sum[i] = { 0,0 };

	cnt = 1;
}

bool Safe(int y, int x)
{
	if (y >= 0 && x >= 0 && y < n && x < n)
		return true;
	return false;
}

bool Dist(int f, int s)
{
	int value = abs(f - s);

	if (value >= l && value <= r)
		return true;
	return false;
}

struct forQ
{
	int y;
	int x;
	int count;
};

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

	cin >> n >> l >> r;

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

	while (loop)
	{
		clear();

		queue<forQ> q;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (condi[i][j] == 0)
				{
					// condition이 0이면 아직 미처리 단계
					q.push({ i,j,cnt });

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

						// 이미 처리했던 나라는 중복되지 않게
						if (condi[here.y][here.x] != 0)
							continue;

						// 꼭 count로 따로 변수로 하지않고 cnt를 사용해도 된다.
						// sum에 first에 나라수 second에 총 인구수를 더해준다
						sum[here.count].first += 1;
						sum[here.count].second += popu[here.y][here.x];

						condi[here.y][here.x] = here.count;

						for (int k = 0; k < 4; k++)
						{
							int dY = here.y + dy[k];
							int dX = here.x + dx[k];

							if (Safe(dY, dX) && 
                            				Dist(popu[here.y][here.x], popu[dY][dX]))
							{
								q.push({ dY,dX,here.count });
							}
						}
					}

					cnt++;
				}
			}
		}

		// 연합국 번호에 따른 인구수 배분
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				popu[i][j] = sum[condi[i][j]].second / sum[condi[i][j]].first;
			}
		}

		loop = false;

		// 루프를 false로 해준 뒤 변한 2개 이상 합쳐진 연합국이 있을 경우 루프 재개
		for (int i = 0; i < cnt; i++)
		{
			if (sum[i].first > 1)
				loop = true;
		}

		if(loop)
			result++;
	}

	cout << result << endl;
}

#삼성A형 #BFS