[C++] 삼성 SW 역량 테스트 기출문제 백준 16234 - 인구 이동

 

 

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

16234번: 인구 이동

 

 

 

#include <bits/stdc++.h>
// [C++] 삼성 SW 역량 테스트 기출문제 백준


int n, l, r;
int map[50][50];
int state[50][50];
int sum, cnt;


void bfs(int i, int j){
	const int dy[] = {-1, 1, 0, 0};
	const int dx[] = {0, 0, -1, 1};

	std::queue<std::pair<int, int>> q;
	state[i][j] = 1;
	++cnt;
	sum += map[i][j];
	q.push({i, j});

	while(!q.empty()){
		auto [y, x] = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir){
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
			if (state[ny][nx] != 0) continue;
			int diff = std::abs(map[y][x] - map[ny][nx]);
			if (diff < l || diff > r) continue;
			state[ny][nx] = 1;
			++cnt;
			sum += map[ny][nx];
			q.push({ny, nx});
		}
	}
}


void update(int i, int j, int val){
	const int dy[] = {-1, 1, 0, 0};
	const int dx[] = {0, 0, -1, 1};

	std::queue<std::pair<int, int>> q;
	state[i][j] = 2;
	map[i][j] = val;
	q.push({i, j});

	while(!q.empty()){
		auto [y, x] = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir){
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
			if (state[ny][nx] != 1) continue;
			state[ny][nx] = 2;
			map[ny][nx] = val;
			q.push({ny, nx});
		}
	}
}


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

	int ret = 0;
	std::cin >> n >> l >> r;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			std::cin >> map[i][j];
		}
	}

	bool flag = true;
	while(flag){
		flag = false;

		for (int i = 0; i < n; ++i){
			for (int j = 0; j < n; ++j){
				if (state[i][j] != 0) continue;
				sum = 0;
				cnt = 0;
				bfs(i, j);
				if (cnt == 1){
					state[i][j] = 2;
				}
				else{
					update(i, j, sum / cnt);
					flag = true;
				}
			}
		}

		if (flag){
			for (int i = 0; i < n; ++i){
				std::fill(state[i], state[i] + n, 0);
			}
			++ret;
		}
		else {
			break;
		}
	}

	std::cout << ret << '\n';
	return 0;
}