BOJ. Population Movement (16234)

Problem: BOJ 16234 — Population Movement · 한국어 · 日本語

For one day, connect neighboring countries when the absolute difference between their populations is between L and R, inclusive. Each connected component containing at least two countries is a union; every country in that union receives the floor of the component’s average population. All unions for the day are determined from the same pre-update grid, then updated together. The process ends on the first day when no border opens, and the answer is the number of days on which at least one union formed.

The border condition is L <= |A - B| <= R because the problem opens a border only when the population difference is not smaller than L and not larger than R. Both endpoints are included. A BFS from each unvisited country collects exactly the countries reachable through open borders. After collecting all components, compute each union’s average and apply it to its members; single-country components remain unchanged. Increment the day count only if at least one component contains multiple countries. Read N, L, R, and every grid value before starting this simulation.

There are N^2 countries and each country and neighboring border is examined a constant number of times per day, so each day takes O(N^2) time. The grid, visited flags, queue, and component lists use O(N^2) memory.

C++17

#include <cstdlib>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

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

    int n, lower, upper;
    cin >> n >> lower >> upper;

    vector<vector<int>> population(n, vector<int>(n));
    for (auto& row : population) {
        for (int& value : row) cin >> value;
    }

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    int days = 0;

    while (true) {
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        vector<vector<pair<int, int>>> unions;

        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < n; ++col) {
                if (visited[row][col]) continue;

                queue<pair<int, int>> pending;
                vector<pair<int, int>> component;
                pending.push({row, col});
                visited[row][col] = true;

                while (!pending.empty()) {
                    const auto [currentRow, currentCol] = pending.front();
                    pending.pop();
                    component.push_back({currentRow, currentCol});

                    for (int direction = 0; direction < 4; ++direction) {
                        const int nextRow = currentRow + dr[direction];
                        const int nextCol = currentCol + dc[direction];
                        if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n) continue;
                        if (visited[nextRow][nextCol]) continue;

                        const int difference = abs(population[currentRow][currentCol] - population[nextRow][nextCol]);
                        if (lower <= difference && difference <= upper) {
                            visited[nextRow][nextCol] = true;
                            pending.push({nextRow, nextCol});
                        }
                    }
                }

                if (component.size() > 1) unions.push_back(move(component));
            }
        }

        if (unions.empty()) break;

        for (const auto& component : unions) {
            int total = 0;
            for (const auto& [row, col] : component) total += population[row][col];
            const int average = total / static_cast<int>(component.size());
            for (const auto& [row, col] : component) population[row][col] = average;
        }
        ++days;
    }

    cout << days << '\n';
    return 0;
}