[백준][16234][c++] 인구 이동

인구 이동 문제 링크

[내 풀이]

알고리즘
한 맵에서 조건에 맞춰 연결되어 있는 좌표들(=연합)을 BFS를 이용해 다 저장한 후에 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)로 값을 update해주면 되고 이러한 update가 map단위로 몇번 일어났는지를 출력하면 된다. 조건에 맞춰 연결되어 있는 좌표들은 서로 인접해 있고 차이가 L이상 R이하 여야 한다. 인접한 것의 기준은 상하좌우이고 간접적으로 연결되어 있는 것도 포함된다.

자료구조
연합들을 모은 vector와 연합 인구수를 모은 vector

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <stdlib.h>
#define N_MAX 51

using namespace std;

int N, L, R;
int A[N_MAX][N_MAX];

int dir_y[4] = { 1,-1,0,0 };
int dir_x[4] = { 0,0,1,-1 };

int move_people() {
	int result = 0;
	
	while (1) {
		bool flag = false;
		bool visited[N_MAX][N_MAX] = { false, };
		vector<queue<pair<int, int>>> part;
		vector<int> num_saved;

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (y == 2 && x == 2) {
					int subn = 0;
				}
				if (visited[y][x]) continue;
				queue<pair<int, int>> q;
				queue<pair<int, int>> saved;
				int num = 0;

				q.push({ y,x });
				saved.push({ y,x });
				num += A[y][x];
				visited[y][x] = true;
				
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();

					for (int dir = 0; dir < 4; dir++) {
						int new_y = cur.first + dir_y[dir];
						int new_x = cur.second + dir_x[dir];

						if (new_y < 0 || new_y >= N || new_x < 0 || new_x >= N) continue;
						if (visited[new_y][new_x]) continue;
						int diff = A[new_y][new_x] - A[cur.first][cur.second];
						if (!(abs(diff) >= L && abs(diff) <= R)) continue;

						q.push({ new_y, new_x });
						saved.push({ new_y, new_x });
						num += A[new_y][new_x];
						visited[new_y][new_x] = true;
					}
				}

				if (saved.size() > 1) {
					part.push_back(saved);
					num_saved.push_back(num);
				}
			}
		}

		if (part.empty()) break;
		else {
			int size_p = part.size();
			for (int p = 0; p < size_p; p++) {
				queue<pair<int, int>> s = part.front();
				int united_num = num_saved[p] / s.size();
				part.erase(part.begin());

				while (!s.empty()) {
					pair<int, int> cur = s.front();
					s.pop();
					A[cur.first][cur.second] = united_num;
				}

			}
			//test_map();
		}

		result++;
	}

	return result;
}


int main() {
	cin >> N >> L >> R;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> A[y][x];
		}
	}

	int ans = move_people();
	cout << ans << "\n";
}

[총평]
쉬운 BFS 응용이었지만 디버깅하느라 1시간 걸렸다...