BOJ 16234 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

문제 해결 전략

인구 이동을 할 때, check 배열로 이미 이동이 됐는지 체크하였다. 한 부분에서 인구 이동이 발생하면, 바로 sum과 cnt를 이용하여

평균값으로 대입해주었다. 이렇게 하지 않으면 한 구역(다수의 땅)에 다른 구역(다수의 땅)이 겹칠 수 있기 때문에 원치 않는 인구 이동이

발생할 수 있다.

 

소스

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define endl "\n"
#define MAX 51
const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
int n, l, r;
int map[MAX][MAX];
bool check[MAX][MAX];
int totalNum;
int range(int temp1, int temp2) {
    if( abs(temp1 - temp2) >= l && abs(temp1 - temp2) <= r )
        return true;
    else
        return false;
}
void bfs(int yy, int xx) {
    int landSum = 0, landCnt = 0;
    queue<pair<int, int>> q;
    queue<pair<int, int>> nq;
    q.push({yy, xx});
    nq.push({yy, xx});
    check[yy][xx] = true;
    landSum += map[yy][xx];
    landCnt++;
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            if(!range(map[y][x], map[ny][nx]) || check[ny][nx]) continue;
            q.push({ny, nx});
            nq.push({ny, nx});
            check[ny][nx] = true;
            landSum += map[ny][nx];
            landCnt++;
        }
    }
    while(!nq.empty()) {
        int y = nq.front().first;
        int x = nq.front().second;
        nq.pop();
        map[y][x] = (landSum / landCnt);
    }
}
int main(int argc, char** argv) {
    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 >> map[i][j];
        }
    }
    while(1) {
        bool flag = true;
        memset(check, 0, sizeof(check));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int dir = 0; dir < 4; dir++) {
                    int ny = i + dy[dir];
                    int nx = j + dx[dir];
                    if(ny < 0 || ny >= n || nx < 0 || nx >= n || check[i][j]) continue;
                    if(!range(map[i][j], map[ny][nx])) continue;
                    bfs(i, j);
                    flag = false;
                }
            }
        }
        if(flag) break;
        totalNum++;
    }
    cout << totalNum;
}