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

  문제  

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

16234번: 인구 이동

---

  풀이  

• 사용 알고리즘 : BFS
• 시간 복잡도 : O(ans * N³)

BFS를 통해 그래프 연결 요소(connected components)를 구하고, 적절히 시뮬레이션을 돌려주어 풀었던 문제입니다.

 

먼저 인접한 각 나라들의 인구수 차이가 L 이상 R 이하라면 국경선이 열리면서 하나의 연합이 형성됩니다. 이 문제를 풀려면 어떤 나라들이 어떻게 연합을 이루는지를 알 필요가 있습니다. 이는 BFS를 돌려주면서 연결 요소를 구해주면 됩니다.

연합의 인구수는 연결 요소에 포함된 나라들의 인구수의 합이 될 거고, 연합을 이루는 칸의 개수는 연결 요소에 포함된 나라들의 개수가 되겠죠.

 

저의 경우에는, 각각의 칸마다 BFS를 새롭게 시도해봅니다. 물론 이미 방문한 칸은 바로 패스해야겠죠. 그렇게 만들어진 연결 요소(연합)가 있다면 바로 인구 수를 새롭게 업데이트 해줍니다. 혹시나 인구 수를 바로 업데이트 하게 된다면 이후에 하는 BFS 탐색에서 인접한 나라들의 인구수 차이를 구할 때 문제가 생길 수 있지 않을까 라는 의문이 들 수 있지만, 이는 잘 생각해보면 방문 체크를 할 때 전부 걸러 낼 수 있습니다.

 

최종적으로, 각각의 나라들마다 BFS를 시도해보는데, 만약 나라의 개수가 2개 이상 포함된 연결 요소의 개수가 0개라면 해당 날에는 인구이동을 할 수 없는 것이죠. 따라서 탐색을 끝내주면 됩니다. 반대로 연결 요소의 개수가 1개 이상이라면 인구 이동이 가능한 날이므로 계속 탐색을 진행해주면 됩니다.

---

  코드  

#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

struct A {
	int x;
	int y;
};

int mmap[51][51];
bool visited[51][51];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool bfs(int x, int y, int n, int l, int r) {
	queue<A> que;
	que.push({x, y});
	visited[x][y] = true;
	int componentCnt = 0;
	int componentPeopleCnt = 0;
	vector<A> v;
	while (!que.empty()) {
		int xx = que.front().x;
		int yy = que.front().y;
		que.pop();
		componentCnt++;
		componentPeopleCnt += mmap[xx][yy];
		v.push_back({xx, yy});
		
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny]) continue;
			if (abs(mmap[xx][yy] - mmap[nx][ny]) < l || abs(mmap[xx][yy] - mmap[nx][ny]) > r) continue;
			visited[nx][ny] = true;
			que.push({nx, ny});
		}
	}
	if (componentCnt >= 2) {
		componentPeopleCnt = componentPeopleCnt / componentCnt;
		for (int i = 0; i < componentCnt; i++) {
			int xx = v[i].x;
			int yy = v[i].y;
			mmap[xx][yy] = componentPeopleCnt;
		}
		return true;
	}
	else return false;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, l, r;
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mmap[i][j];
		}
	}
	int ans = 0;
	while (1) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = false;
			}
		}
		bool flag = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				if (bfs(i, j, n, l, r)) flag = true;
			}
		}
		if (flag) ans++;
		else break;
	}
	cout << ans;
	return 0;
}