[백준] 인구이동 (16234번/C++)

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

16234번: 인구 이동

코드 설명

삼성 기출답게 bfs+구현 문제이다.

문제를 똑바로 읽고 설계를 해야 하는 문제이다. 기본적인 BFS를 이용한 순회 이동 문제이기도 하다.

 

함정아닌 함정이 많다.  전체 while문을 통해서 한번 인구이동 시켜준 후 다시 map을 전체 탐색하면서 인구이동이 가능한지 탐색해줘야 한다.

 

즉 , 한번 순회한다고 끝이 아니다

또한 vector하나를 이용하여 인구 이동시켜야 할 좌표를 가져온 후 main문에서 bfs탈출 후 좌표를 바꿔준다.

 

순회 한 번마다 정답이 +1 씩이라는 것을 잊지 말자

 

전체 순회를 하였을 때 한 칸도 이동할 칸이 없다면 그제야 break로 탈출시켜준다.

 

 

코드

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
int N, L, R;
int map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int change_map[51][51];
	bool flag = false;
	int aanswer;

vector<pair<int, int> > a;
void bfs(int y, int x) {
	int sum = 0;
	int cnt = 0;
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;
	
	
	a.push_back({ y,x });


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

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (!visited[ny][nx]) {
				if (abs(map[y][x] - map[ny][nx]) >= L && abs(map[y][x] - map[ny][nx]) <= R) {
					q.push({ ny,nx });
					visited[ny][nx] = true;
					a.push_back({ ny,nx });
				}
			}
		}
	}
	
	if (a.size() > 1) {
		cnt = a.size();
		for (int i = 0; i < cnt; i++) {
			sum += map[a[i].first][a[i].second];
		}
		for (int i = 0; i < cnt; i++) {
			map[a[i].first][a[i].second] = sum / cnt;
		}
		
		flag = true;

	}

	a.clear();
	
}

int main() {
	cin >> N >> L >> R;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
		}
	}
	while (1) {
		memset(visited, false, sizeof(visited));
		
		flag = false;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				//바뀔게 있는가? 
				//이미 바뀐 index인가 
				if (!visited[y][x]) {
					bfs(y, x);
				}


			}
		}
	
		if (flag == false) break;
		else aanswer++;
	}

	cout << aanswer;
	return 0;
}