BOJ : 16234 인구 이동

---

[BOJ 16234(G5) 리뷰]

 

풀고 나면 굉장히 간단한 문제인데, 풀기 전에는 왜이렇게 어려운지 모르겠다.

처음에 문제 이해하는게 좀 힘들었는데 문제를 잘 살펴보니 전형적인 BFS문제이다.

BFS를 통해 국경선이 열리는 조건에 대해 확인을 한 후 만족하는 그룹을 하나의 연합으로 보면 된다.

 

처음에는 먼저 BFS를 수행하여 각 국가마다 연합 INDEX를 부여하고 연합INDEX를 토대로 BFS를 다시 수행하여 값을 바꿔주려고 했는데 굉장히 비효율적인 작업임을 알아챘다.

그래서 벡터를 만들어 처음 BFS를 수행할때 각 연합INDEX에 바뀌게 될 값을 저장하고, 반복문을 통하여 연합INDEX에 맞게 저장된 값으로 바꿔주는 작업을 수행했다.

 

결과적으로 다음과 같다.

1.numbering (각 국가에 대해 국경이 열린지 확인하고 국경이 열려있는 국가에 대해 연합번호를 부여한다.)

2.changing (국가별 부여된 연합index를 토대로 vector에 저장된값으로 바꿔준다.)

 

위 과정을 반복하며, 국가이동이 더 이상 없을경우 반복을 멈춰주면 된다.

---

#include <iostream>
#include <queue>
#include <deque>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
#define X first
#define Y second
int N, L, R;
int nation[51][51];
int guild[51][51];
vector <int> value;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int numbering()
{
	int ret = false;
	int number = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (guild[i][j]) continue;
			queue<pair<int, int>> Q;
			guild[i][j] = number;
			Q.push({ i,j });
			int cnt = 1;
			int total = nation[i][j];
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
					if (guild[nx][ny]) continue;
					int people = abs(nation[cur.X][cur.Y] - nation[nx][ny]);
					if (people >= L && people <= R) //국경 공유
					{
						Q.push({ nx,ny });
						guild[nx][ny] = number;
						cnt++;
						total += nation[nx][ny];
						ret = true;
					}
				}
			}
			value.push_back(total/cnt);
			number++;
		}
	}
	return ret;
}

void changing()
{
	int size = value.size();
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			nation[i][j] = value[guild[i][j] - 1];
		}
	}
}
int main()
{
	cin >> N >> L >> R;
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> nation[i][j];
		}
	}

	int ans = 0;
	while (1)
	{
		for (int i = 0; i < N; i++)
		{
			fill(guild[i], guild[i] + N, 0);
		}
		value.clear();
		if (!numbering()) break;;
		changing();
		ans++;
	}
	

	cout << ans;

}