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

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

16234번: 인구 이동

bfs 혹은 dfs를 활용하여 해결할 수 있다.

 

인구이동 조건과, 방문 여부가 탐색 진행의 기준이 된다.

 

for(for(bfs)) 구조로 해결할 수 있다.

 

for(for 을 완전히 탈출할 때 까지가 한 번의 인구이동 날이라고 할 수 있다.

 

따라서 이를 무한루프로 감싸서, 인구의 이동이 없는 경우 무한루프를 탈출하는 구조로 해결하면 된다.

 

 

그런데, 인구 이동 조건을 만족하더라도, 그 자리에서 인구수를 바로 갱신할 수가 없다.

 

일단 국경을 개방할 수 있는 지점을 모두 찾아내야 하기 때문에, 일단 한 번의 bfs가 다 종료되어야 인구수를 갱신할 수 있다. 방문처리된 지점들(큐에 삽입된 적이 있는 지점들)이 갱신의 대상이기 때문에, 이 좌표들을 차례로 백터에 저장해준다.

 

이후에 벡터의 크기가 연합국의 숫자이고, 인구수의 합은 큐에 삽입하면서 기억해 둘 것이다.

 

한번의 인구 이동이 모두 끝났는데, 변화가 없다면 무한 루프를 종료하고, 그렇지 않다면 방문처리 배열을 초기화해준 이후에 인구이동을 다시 시작해주면 된다.

 

#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int N, L, R, m[51][51];
bool bor[51][51]; //방문 처리 배열
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

queue<pair<int, int> > q;
bool updated = false;
int idxSum = 0;
vector<pair<int, int> > v;
void bfs(pair<int, int> start) {
	q.push(start);
	bor[start.first][start.second] = true;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= N || nc >= N || bor[nr][nc])
				continue;
			if (abs(m[nr][nc] - m[cur.first][cur.second]) >= L &&
				abs(m[nr][nc] - m[cur.first][cur.second]) <= R) {
				q.push({ nr, nc });
				bor[nr][nc] = true; 
				
				v.push_back({ nr, nc });
				idxSum += m[nr][nc];
			}
		}
	}
}
void init() {
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			bor[i][j] = 0;
}
int main(void) {
	ios::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 >> m[i][j];

	int res = 0;
	while (1) {
		updated = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!bor[i][j]) {
					v.clear();
					v.push_back({ i,j }); 
					idxSum = m[i][j];
					bfs({ i, j });
				}
				//열린 국경이 있으면
				if (v.size() >= 2) { //한 연합 내의 국가 개수
					updated = true;
					int val = idxSum / v.size();
					for (int i = 0; i < v.size(); i++) {
						m[v[i].first][v[i].second] = val;
					}
				}
			}
		}
		if (updated) res++;
		else break;
		init();
	}
	cout << res << '\n';
	return 0;
}