[BOJ 16234] 인구 이동

🔗Link

문제
풀이

💡Idea

이차원배열에서의 bfs라고 생각하면 된다. 다만, 이동 조건은 각 땅의 차이가 L이상 R일 때만이다. 보통 bfs라면 queue를 썼겠지만, 나중에 방문한 땅들에 다시 접근하여 인구수를 전부 같은 값으로 설정해줘야 하기 때문에, 방문한 땅들을 따로 다시 모아두기 보다는, queue 대신 vector를 써서 나중에 for문으로 다시 접근하였다.

🔑Code

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int N, L, R;
int A[50][50];
int vis[50][50];

bool BFS(int x, int y){
    vector<pair<int,int>> V;

    vis[x][y] = true;
    V.emplace_back(x,y);

    int sum = A[x][y];
    int cnt = 1;

    for(int k = 0; k < V.size(); k++){
        auto cur = V[k];
        for(int i = 0; i < 4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0||ny < 0||nx >= N||ny >= N) continue;
            if(vis[nx][ny]) continue;
            int diff = abs(A[cur.X][cur.Y] - A[nx][ny]);
            if(diff < L || diff > R) continue;

            vis[nx][ny] = true;
            V.emplace_back(nx,ny);
            sum += A[nx][ny];
            cnt++;
        }
    }
    int div = sum / cnt;
    for(auto cur : V){
        A[cur.X][cur.Y] = div;
    }
    return cnt > 1;
}

bool SpendADay(){
    bool hasMove = false;

    for(int i = 0; i < N; i++)
        fill(vis[i], vis[i]+N, false);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(vis[i][j]) continue;
            hasMove |= BFS(i,j);
        }
    }
    return hasMove;
}

int main(void){
    ios_base::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 >> A[i][j];
        }
    }

    int days = 0;
    while(SpendADay())
        days++;

    cout << days;

    return 0;
}

🗨️ Side Notes

bfs를 구현할 때 항상 queue를 쓰고 vector를 써보는 건 처음인데, 방문했던 점들을 다시 접근해야할 때 괜찮은 방법인 것 같다.