[백준][16234번] 인구 이동

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

16234번: 인구 이동

풀이과정

 

1. 인구이동이 일어나는 인전합 나라를 체크하기 위해 BFS를 사용했다.

 

2. visited배열을 통해 이미 방문한 나라는 또 방문하지 않는다.

 

3. 동시에 여러 구역에서 인구이동이 일어 날 수 있으므로, 모든 구역을 다 체크해야 한다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
using namespace std;
int map[50][50];
int visited[50][50];
int N, R, L;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int moving = 0;
bool checkOpen(int n1, int n2)
{
	int result = abs(n1 - n2);
	if (result >= L && result <= R) {
		return true;
	}
	return false;
}

void bfs(int x, int y)
{
	queue<pair<int, int>> que;
	vector<pair<int, int>> v;
	int sum = map[y][x];
	que.push(make_pair(x, y));
	v.push_back(make_pair(x, y));
	visited[y][x] = 1;
	while (!que.empty()) {
		int queSize = que.size();
		for (int i = 0; i < queSize; i++) {
			pair<int, int> p = que.front(); que.pop();
			for (int j = 0; j < 4; j++) {
				int nx = p.first + dx[j];
				int ny = p.second + dy[j];
				if (visited[ny][nx] == 0 && nx >= 0 && ny >= 0 && nx < N && ny < N) {
					if (checkOpen(map[p.second][p.first], map[ny][nx])) {
						visited[ny][nx] = 1;

						sum += map[ny][nx];
						pair<int, int> tmp = make_pair(nx, ny);
						que.push(tmp);
						v.push_back(tmp);
					}
				}
			}
		}
	}

	int result = sum / v.size();
	for (int i = 0; i < v.size(); i++) {
		map[v[i].second][v[i].first] = result;
	}
	if (v.size() > 1) {
		moving = 1;
	}
}

int solution()
{
	int answer = 0;
	while (1) {
		moving = 0;
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j]) continue;
				bfs(j, i);
			}
		}
		if (!moving) {
			return answer;
		}
		answer++;
	}
}

int main()
{
	scanf("%d %d %d", &N, &L, &R);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	printf("%d\n", solution());
}

 

결과