[BOJ/16234번인구이동] c++ / BFS

문제

각 나라의 인구 수가 주어졌을 때, 인구 이동이 며칠동안 발생하는지 구하는 문제

-인접한 나라의 인구 수 차이가 L이상 R이하일 때 국경선이 열림

-국경선이 열려 인접하게된 국가를 연합국가라 함

-연합 국가의 각 나라의 인구 수는 '연합국가의 인구 수/ 연합국가의 수'가 됨

 

생각

국경선이 열리는 것까진 일반 BFS 문제와 같겠다 생각함

근데 문제가 잘 이해가 안됐음 구글링해서 이해한 결과

국경선을 여는걸 한번만 하는게 아니라 인구 이동 후에도 또 하고, 또 하고 하는 식인걸 깨달았음!

 

문제풀이

0.연합국이 없을 때까지 아래 과정을 계속 반복( cnt 개수를 셈 )

1.국경선을 열어줘야함 BFS

1-1.방문표시가 없다면, 큐에 푸쉬

1-2.상하좌우의 나라와의 인구 수 차이가 L이상 R이하이면, 방문표시 + 국경선 넘었다는 표시(areaNum) + 큐에 푸쉬

2.연합국(국경선이 열린 나라)의 인구를 일치 시켜야 함

2-1.국경선이 열려있고 방문표시가 없다면, 인구이동 시작

2-2.큐 두개를 만들어줌(하나는 나라 개수 + 인구 수 구하는 용도/ 다른 하나는 위에서 구한 인구수를 board에 대입할 때 쓰는 용도 )

2-3.상하좌우의 나라가 기준이 되는 나라와 연합국이고, 방문표시가 없다면 방문표시 + 전체 인구수에 인구 수 추가 + 나라 개수 추가 + 큐에 푸쉬 

(자꾸 런타임 에러 뜨길래 뭐가 문제인가 했더니, moveQ pop 해줘야하는걸, Q pop 해주고 있었음 ... ㅠㅠ )

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int board[51][51];
int vis[51][51], ckOpen[51][51];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int L, R, N, cnt=0;
int haveToMove() {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ )
            if ( ckOpen[i][j] ) 
                return 1;
    }
    return 0;
}
void movePopulation(int i, int j) {
    queue<pair<int, int>> Q;
    queue<pair<int, int>> moveQ;

    int area = 1;
    int areaNum = ckOpen[i][j];
    int totalPopulation = board[i][j];
    vis[i][j] = 1;
    Q.push({i, j});
    moveQ.push({i, j});

    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if ( nx < 0 || nx >= N || ny < 0 || ny >= N ) continue;
            if ( ckOpen[nx][ny] != areaNum || !ckOpen[nx][ny] || vis[nx][ny] ) continue;

            vis[nx][ny] = 1;
            area++;
            totalPopulation += board[nx][ny];
            Q.push({nx, ny});
            moveQ.push({nx, ny});
        }
    }

    int Population = totalPopulation / area;
    while (!moveQ.empty()) {
        pair<int, int> cur = moveQ.front(); moveQ.pop(); // 여기서 Q 팝 하니까 오류남 ㅋㅋ
        board[cur.X][cur.Y] = Population;
    }
}
void OpenLine() {
    queue<pair<int, int>> Q;
    int areaNum = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( vis[i][j] ) continue;
            areaNum++;
            vis[i][j] = 1;
            Q.push({i,j});

            while (!Q.empty()) {
                pair<int, int> cur = Q.front(); Q.pop();

                for ( int dir = 0; dir < 4; dir++ ) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if ( nx < 0 || nx >= N || ny < 0 || ny >= N ) continue;
                    if ( vis[nx][ny] ) continue;
                    int diff = abs(board[cur.X][cur.Y]-board[nx][ny]);
                    if ( diff < L || diff > R ) continue;

                    vis[nx][ny] = 1;
                    ckOpen[cur.X][cur.Y] = ckOpen[nx][ny] = areaNum;
                    Q.push({nx, ny});
                }
            }
        }
    }
}
void Moveto() {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( !ckOpen[i][j] || vis[i][j] ) continue;
            movePopulation(i, j);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.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(1) {
        memset(vis, 0, sizeof(vis));
        memset(ckOpen, 0, sizeof(ckOpen));

        OpenLine();
        memset(vis, 0, sizeof(vis));

        if ( !haveToMove() ) break;
        Moveto();
        cnt++;
    }

    cout << cnt;
}