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

문제

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

---

문제 요약

N × N 크기의 땅이 있고, 땅은 1 × 1개의 칸으로 나누어져 있다.

 

각각의 땅에는 나라가 하나씩 존재하며, 그곳에는 사람들이 살고 있다.

 

오늘부터 인구 이동이 시작된다.

 

1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두나라가 공유하는 국경선을 하루 동안 연다.

2. 위 조건에 맞는 국경선이 모두 열리고, 인구 이동이 시작된다.

3. 국경선이 열려 있어 인접한 칸을 이용해 이동할 수 있으면, 그 나라들은 하루 동안 연합을 이룬다.

4. 연합을 이루고 있는 각 칸의 인구 수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다.

5. 연합을 해체하고, 모든 국경선을 닫는다.

 

각 나라의 인구 수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int board[55][55];

int n, L, R;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

// 반복 일수
int res;

bool visited[55][55];

// 하루 동안 인구 이동이 발생했는지 여부
bool isMoved;

void bfs(int start_x, int start_y) {
	// 초기 값 큐에 삽입
	queue<pair<int, int>> q;
	q.push(make_pair(start_x, start_y));

	// 초기 값 방문 체크
	visited[start_x][start_y] = true;
	
	// 초기 값 연합에 포함
	vector<pair<int, int>> v;
	v.push_back({ start_x, start_y });

	// 연합 내 인구 수 계산을 위한 값 초기화
	int cnt = 1;
	int sum = board[start_x][start_y];

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

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny]) continue;

			// 인구 차이 계산
			int gap = abs(board[x][y] - board[nx][ny]);
			if (gap < L || gap > R) continue;

			visited[nx][ny] = true;
			q.push(make_pair(nx, ny));

			v.push_back({ nx, ny });

			cnt++;
			sum += board[nx][ny];
		}
	}

	// 국경선이 열리는 나라가 1개라도 존재할 경우
	if (cnt > 1) isMoved = true;

	// 연합 인구수 계산
	for (auto& area : v) {
		int area_x = area.first;
		int area_y = area.second;
		board[area_x][area_y] = sum / cnt;
	}
}

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> L >> R;

	// 각 나라의 인구 수 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	
	while (true) {
		// 인구 이동 여부 초기화
		isMoved = false;

		// BFS 탐색 전 방문 여부 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = false;
			}
		}

		// 모든 칸에 대해 BFS 탐색을 통해 연합 내 각 칸의 인구수 재설정
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				bfs(i, j);
			}
		}

		// 인구 이동이 없는 경우
		if (!isMoved) break;

		// 날짜 계산
		res++;
	}
	
	cout << res;

	return 0;
}

---

코드 설명

BFS 탐색을 통해 문제를 해결한다.

 

1. 각 나라의 인구 수를 입력 받는다.

 

2. 모든 나라에 대해 BFS 탐색을 통해 연합이 가능한 나라를 찾고, 각 연합의 인구 수를 갱신한다.(반복한다.)

 

3. 각 나라 간 인구 차이가 조건에 맞는 경우가 없어서 인구 이동이 한 번도 없을 경우, 반복을 종료한다.

 

4. 반복 횟수를 출력한다.

---

고찰

초기에는, BFS 탐색이 끝난 후에 방문 체크된 나라를 연합으로 보고, 모두 갱신하였다.

하지만, 하루에 여러 연합이 존재할 수 있다는 것이 문제점이었다.

 

위처럼 코드를 작성했을 경우, 이전 BFS에서 찾은 연합에 속한 나라도 함께 인구 수가 갱신되는 문제가 있다.