백준 16234번: 인구 이동 (C++)

문제 링크 : https://www.acmicpc.net/problem/16234

 

단순한 bfs 문제였습니다.

1. 한 좌표에서 bfs로 이차원 배열을 탐색합니다. 탐색 되지 않은 좌표들은 다시 bfs를 돌려줍니다. (다음 노드가 L 이상 R 이하인 부분만 탐색하는 bfs.)

2. 한 좌표에서 bfs를 돌려 탐색 된 부분들은 한 연합입니다. 연합나라들의 수를 분배합니다.(bfs를 돌릴 때 vector에 각 좌표를 저장해두면 쉽게 수를 분배할 수 있습니다.

3. 한 연합 안에서 사람 수들이 모두 같지 않으면 결국 이동을 해야 합니다.

4. 이동할 필요가 없으면 종료해줍니다.

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

using namespace std;

int n, L, R;
int people[52][52];
bool check[52][52];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

bool bfs(int startx, int starty)  //bfs로 탐색하고 연합들 인구 수 분배
{
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	q.push(make_pair(startx, starty));
	check[startx][starty] = true;

	int sum = 0;
	int count = 0;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		sum += people[x][y];          //탐색하면서 사람들 수 더하기
		count++;
		v.push_back(make_pair(x,y));

		for (int d = 0; d < 4; d++)    //방향 선택
		{
			int nextx = x + dir[d][0];
			int nexty = y + dir[d][1];
			if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= n)continue;
			if (check[nextx][nexty])continue;

			int gap = abs(people[x][y] - people[nextx][nexty]);
			if (gap >= L && gap <= R)   
			{
				check[nextx][nexty] = true;
				q.push(make_pair(nextx, nexty));
			}
		}
	}

	int standard = people[v[0].first][v[0].second];
	bool moving = false;;
	for (int i = 0; i < v.size(); i++)           //인구 수 분배
	{
		int x = v[i].first;
		int y = v[i].second;
		if (standard != people[x][y])moving = true;  //값이 모두 같지 않으면 이동해야함
		people[x][y] = sum / count;
	}
	return moving;
}

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

	cin >> n >> L >> R;

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

	int count = 0;
	while (1)
	{
		bool moving = false;
		fill(&check[0][0], &check[49][50], 0);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (check[i][j])continue;
				if(bfs(i, j))moving=true; //한번이라도 이동하면 moving이 true로 됨
			}
		}
		if (moving == false)break;  //이동한적이없으면 탈출
		count++;
	}

	cout << count << "\n";

	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.