[16234] 인구 이동

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

16234번: 인구 이동

<문제>

하나의 턴이 진행될 때마다 아래의 과정을 구현해줘야 한다.

1. 인구이동이 발생할 수 있는지를 판별

2. 발생할 수 있는 모든 인구이동을 '한 번에' 진행

 

 

1에 대한 판별을 canMerge(sy, sx)의 함수로 만들고, 모든 sy와 sx에 대해서 검사를 진행한다.

즉, 매 턴마다 canMerge함수를 N^2번 호출해주었다.

 

canMerge가 true를 반환한다면 2칸 이상의 연합이 만들어질 수 있다는 의미이기에 인구이동을 진행해주어야 한다.

이를 bfs를 사용하여 모든 연합의 구성원을 판별해주었다.

업데이트와 탐색을 동시에 진행할 수 없고, bfs가 끝난 후(큐가 빈 뒤에)에 진행해야 올바르게 시뮬레이션이 진행된다.

 

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <algorithm>
#include <queue>
using namespace std;
int a[103][103], n, l, r;
bool visit[103][103];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int update_Y[2501], update_X[2501];
queue<int> q;
bool canMerge(int sy, int sx) {
    int i, y, x;
    for (i = 0; i < 4; i++) {
        y = sy + dy[i];
        x = sx + dx[i];
        if (y < 0 || x < 0 || y >= n || x >= n) continue;
        if (abs(a[y][x] - a[sy][sx]) >= l && abs(a[y][x] - a[sy][sx]) <= r)
            return true;
    }
    return false;
}
int update(int sy, int sx) {
    int i, j, sum = 0, ty, tx, y, x, cnt;
    bool flag;
    q.push(sy);
    q.push(sx);
    sum = a[sy][sx];
    cnt = 1;
    memset(update_Y, 0, sizeof(update_Y));
    memset(update_X, 0, sizeof(update_X));
    update_Y[0] = sy;
    update_X[0] = sx;
    visit[sy][sx] = true;
    flag = false;
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || x >= n || y >= n) continue;
            if (visit[y][x] == false && abs(a[y][x] - a[ty][tx]) >= l &&
                abs(a[y][x] - a[ty][tx]) <= r) {
                flag = true;
                update_Y[cnt] = y;
                update_X[cnt] = x;
                sum += a[y][x];
                cnt++;
                visit[y][x] = true;
                q.push(y);
                q.push(x);
            }
        }
    }
    if (cnt < 2 && flag == false) return -1;
    int num = sum / cnt;
    for (i = 0; i < cnt && i < 2501; i++) {
        a[update_Y[i]][update_X[i]] = num;
    }
    return 0;
}
 
int main(void) {
    int i, j, res, day;
    bool key;
    scanf("%d %d %d", &n, &l, &r);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) scanf("%d", &a[i][j]);
    day = 0;
    res = 0;
    key = true;
    while (1) {
        key = true;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (visit[i][j] == 0 && canMerge(i, j)) {
                    res = update(i, j);
                    if (res == 0) key = false;
                }
            }
        }
        if (key == true) break;
        day++;
        memset(visit, false, sizeof(visit));
    }
    printf("%d", day);
    return 0;
}