[백준] 16234 - 인구 이동

생각보다 시간이 오래 안걸렸던 문제...

디버깅하느라 시간 오래 쓴줄 알았는데 1시간도 안걸렸다

그냥 문제 조건에 맞게 BFS만 잘 던져주면 쓕하고 풀리는 문제였다.

2. 단지 번호 붙이기 처럼 입력된 조건 범위 내에 차이가 나는 국가들을 BFS로 찾으면서 그 값을 더하고, 갯수를 센다.

3. 함수 종료 전, 찾은 국가들은 check배열에 모두 더한 숫자 / 국가 숫자 로 나누어 갱신

4. map이 check배열과 똑같다면 인구 이동이 없었던 것으로 간주하여 while문 탈출, 아니라면 map을 check배열로 갱신하고, 동시에 check배열을 초기화

이 과정만 잘 구현해 준다면 문제 없이 풀리는 문제이다.

#include <iostream>
#define MX 52
#define ABS(X) ((X) > 0? (X) : -(X))
using namespace std;
 
struct PEOPLE {
    int x, y;
}q[MX*MX];
 
int map[MX][MX], check[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, L, R, dab;
 
bool mapcom()
{
    for(int i = 0; i<N; i++)
        for (int j = 0; j < N; j++)
            if (map[i][j] != check[i][j]) return true;
    return false;
}
 
void bfs(int x, int y)
{
    int st, ed, ix, iy, nx, ny, cnt, sum;
    st = ed = -1;
    cnt = sum = 0;
    q[++st].x = x; q[st].y = y; cnt++; sum += map[y][x], check[y][x] = 1;
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++)
        {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || check[ny][nx]) continue;
            if (!(L <= ABS(map[iy][ix] - map[ny][nx]) && ABS(map[iy][ix] - map[ny][nx]) <= R)) continue;
            q[++st].x = nx; q[st].y = ny; sum += map[ny][nx]; cnt++; check[ny][nx] = 1;
        }
    }
    for (int i = 0; i <= ed; i++)
        check[q[i].y][q[i].x] = sum / cnt;
}
 
int main(void)
{
    cin >> N >> L >> R;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
    while(1)
    {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (!check[i][j])
                    bfs(j, i);
        if (mapcom()) dab++;
        else break;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                map[i][j] = check[i][j];
                check[i][j] = 0;
            }
    }
    cout << dab << endl;
    return 0;
}