[백준 16234] 인구 이동 (C++)

문제

백준 16234

16234번: 인구 이동

풀이

bfs로 나라를 돌면서 인구 수 차가 일정 범위 이내라면 q, checkq에 push 합니다.

bfs가 끝난 뒤 checkq에 있는 나라들의 인구를 같게 만들어줍니다.

인구 이동이 발생하지 않을 때 까지 이 과정을 반복하고, 횟수를 출력합니다.

소스 코드

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
int popul[50][50];
int N, L, R;
bool visited[50][50];
bool canmove = true;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int cnt = 0;
void bfs(int sx, int sy)
{
    if (visited[sy][sx])
        return;
    visited[sy][sx] = true;
    queue<pair<int, int>> q;
    queue < pair<int, int>> checkq; //국경 열린 적이 있는 나라의 x좌표와 y좌표 저장하는 queue
    q.push(make_pair(sx, sy));
    checkq.push(make_pair(sx, sy));
    int popsum = 0;
    popsum += popul[sy][sx];
    int country = 0;
    country++;
    while (!q.empty())
    {
        int x, y;
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int sub = abs(popul[y][x] - popul[ny][nx]);
            if (nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if (sub >= L && sub <= R && !visited[ny][nx])
                {
                    visited[ny][nx] = true;
                    country++;
                    popsum += popul[ny][nx];
                    canmove = true;
                    q.push(make_pair(nx, ny));
                    checkq.push(make_pair(nx, ny));
                }
            }
        }
    }
    //bfs 끝난 후에 국경이 열린 나라들 인구 같게 하기
    while (!checkq.empty())
    {
        int qx = checkq.front().first;
        int qy = checkq.front().second;
        popul[qy][qx] = popsum / country;
        checkq.pop();
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> L >> R;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> popul[i][j];
        }
    }
    while (1)
    {
        canmove = false;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                bfs(j, i);
            }
        }
        //국경 열린 적이 없다면
        if (!canmove)
            break;
        //국경 열린 적이 있다면 cnt늘려주고, 초기화해 준 다음 다시 bfs
        cnt++;
        memset(visited, false, sizeof(visited));
    }
    cout << cnt;
    return 0;
}