BOJ::16234 인구 이동

시사점

이해(4)

설계, 손 코딩(2)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(8)

함수 List

업데이트 되는 변수

실제 구현

구현 후 코드리뷰 + 예제 돌려보기(x)

#include<bits/stdc++.h>
#define endl '\n'
#define se second
#define fi first
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int MAXN = 50;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};

int n, L, R;
int a[MAXN][MAXN];
bool seen[MAXN][MAXN];
queue<pair<int,int> >q;
void input(){
    cin >> n >> L >> R;
    rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
}
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=n);}
bool bfs(int sx, int sy){
    queue<pair<int,int> > bq;
    int sum = 0;
    bool ret = false;

    q.push({sx, sy});
    seen[sx][sy]=  true;
    while(!q.empty()){
        int x = q.front().fi, y = q.front().se; q.pop();
        sum += a[x][y];
        bq.push({x, y});
        rep(i, 0, 4){
            int nx = x+dx[i], ny = y+dy[i];
            if(over(nx, ny) || seen[nx][ny]) continue;
            int diff = abs(a[nx][ny] - a[x][y]);
            if(L<= diff && diff <= R){
                ret |= true;
                seen[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    if(bq.size() > 1){
        int mean = sum / (int) bq.size();
        while(!bq.empty()){
            int x = bq.front().fi, y = bq.front().se; bq.pop();
            a[x][y] = mean;
        }
    }
    return ret;
}
int process(){
    input();
    int t = 0;
    while(true){
        bool found = false;
        memset(seen, false, sizeof(seen));
        rep(i, 0, n){
            rep(j, 0, n){
                if(!seen[i][j]){
                    found |= bfs(i, j);
                }
            }
        }
        if(!found) return t;
        t++;
    }
    return -1;
}

int main(){
#ifdef DEBUG
    freopen("input.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << process() << endl;
    return 0;
}

디버깅(x)

좋은 코드

최적화