[BOJ] 16234 : 인구 이동

문제 링크

16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

BFS를 이용한 구현문제.

풀이

임의의 나라에서 인접한 나라와 인구 수가 L이상 R이하 만큼 차이나면 국경을 공유하게 된다. 그리고 국경을 공유한 나라들은 연합이라고 하고 연합국들의 인구는 (연합국의 총 인구수 / 연합국의 수) 로 통일된다.

각 나라를 돌면서 임의의 나라의 인접국중에 인구차이가 L이상 R이하를 만족하는 인접국이 하나라도 있다면 그 임의의 나라에서 BFS탐색을 시작한다. BFS는 인접한 나라 중 인구차이가 L이상 R이하를 만족하는 인접국으로만 이동한다

탐색하면서 모든 연합국의 좌표를 벡터에 넣어두고 마지막에 인구를 통일시켰다.

그리고 BFS 탐색을 시작할 임의의 나라가 한 군데도 없다면 그때는 루프를 탈출한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 50 + 5;
int A[MAX_N][MAX_N];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int N, L, R;
bool visited[MAX_N][MAX_N];
 
bool is_ok(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= N || visited[y][x])
        return false;
    return true;
}
 
bool can_open(int y, int x) {
    for (int i = 0; i < 4; i++) {
        pair<int, int> next = { y + dy[i], x + dx[i] };
        if (is_ok(next.first, next.second)) {
            int diff = abs(A[y][x] - A[next.first][next.second]);
            if (diff >= L && diff <= R)
                return true;
        }
    }
    return false;
}
 
void bfs(int y, int x) {
    queue <pair<int, int>> q;
    q.push({ y,x });
    int Sum = 0;
    vector<pair<int, int>> Union;
    while (!q.empty()) {
        pair<int, int> now = { q.front().first, q.front().second };
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        Sum += A[now.first][now.second];
        Union.push_back(now);
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next.first, next.second)) {
                int diff = abs(A[now.first][now.second] - A[next.first][next.second]);
                if (diff >= L && diff <= R)
                    q.push(next);
            }
        }
    }
    int Value = Sum / Union.size();
 
    for (int i = 0; i < Union.size(); i++) {
        A[Union[i].first][Union[i].second] = Value;
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> L >> R;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> A[i][j];
 
    bool chk = false;
    int ans = 0;
    while (!chk) {
        chk = true;
        memset(visited, false, sizeof(visited));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && can_open(i, j)) {
                    if (chk)
                        ans++;
                    bfs(i, j);
                    chk = false;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}