[백준/C++] 16234번 인구 이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

구현 + bfs 문제라서 조금 까다로웠다. 보통 구현, 시뮬레이션 이쪽 문제들은 꼼꼼히 읽고 자잘하게 챙겨줘야하는 것들이 많으니 유의하시길 바란다!

우선, 원소 하나하나에 대해 bfs를 해준다.

bfs에 들어가기 전에 연합 정보를 저장할 벡터를 이용해 벡터에 탐색을 '시작하는' 곳의 좌표를 넣어주고, 연합의 인구 수를 계산할 변수인 sum에 현재 나라의 인구 수를 저장해준다.

bfs에서는 이웃한 나라와의 인구 차이가 L이상 R이하면은 연합이 된다!

그러므로 벡터에 이웃나라의 좌표정보를 저장해주고, sum 변수에 인구 수를 누적해준다. 여느 bfs와 마찬가지로 방문처리 해주고, 연합이 계속해서 이어질 수 있으므로 큐에 좌표를 넣어서 탐색을 계속 진행한다.

벡터의 사이즈가 2 이상이면 연합이 존재하므로 연합 정보를 계산해주면 된다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int N,L,R;
int board[51][51];
queue<pair<int,int>> q;
vector<pair<int,int>> v;
bool visited[51][51];
int sum =0;

void bfs(int r,int c) {
    q.push({r,c});
    visited[r][c] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;

            int diff = abs(board[x][y] - board[nx][ny]);
            if (L <= diff && diff <= R) {
                v.push_back({nx,ny});
                sum += board[nx][ny];
                q.push({nx,ny});
                visited[nx][ny]=true;
            }
        }
    }
}

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


    cin >> N >> L >> R;

    for(int i=0; i<N;i++){
        for(int j=0; j<N;j++){
            cin >> board[i][j];
        }
    }
    int ans=0;
    bool flag = true;
    while(flag){
        flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    v.clear();
                    v.push_back({ i,j });
                    sum = board[i][j];
                    bfs(i,j);
                }
                if (v.size() >= 2) {
                    flag = true; //연합 체크
                    for (int k= 0; k < v.size(); k++) {
                        int r = v[k].first;
                        int c = v[k].second;
                        int cnt = v.size();
                        board[r][c] = sum / cnt; //평균 갱신
                    }
                }
            }
        }
        if (flag) ans++;

        memset(visited,false,sizeof(visited));
    }
    cout << ans;
    return 0;
}