백준 16234 인구 이동 (C++)

16234번: 인구 이동

단순한 BFS 문제에서 조금 더 생각을 해야하는 문제였다.
총 3가지의 루틴을 반복한다.

1. 맵 처음과 끝까지 반복문을 돌며 BFS가 가능한 곳의 좌표를 찾는다.
2. BFS를 돌며 건에 해당하는 좌표들을 구해 맵의 값을 바꿔준 후 다시 BFS가 가능한 좌표를 찾는다.
3. BFS가 가능한 좌표를 찾지 못할 때까지 이를 반복한다.

solution() 함수의 코드를 보면 visit 배열과 isTrue() 함수를 사용하여 BFS가 가능한 지 확인을 한다. 처음 알고리즘 구상을 할 때 visit 만을 이용하면 될거라고 생각을 해 isTrue()를 생각하지 않았고 당연히 시간 초과가 됐었다. 반복문 내에서 BFS를 사용할 때는 조건문을 만들 때 BFS 가능 유무도 추가될 수 있다는 점을 주의하자.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int N, L, R, res = 0;
int A[51][51];
bool visit[51][51];
bool check = true;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

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

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

        int dif = abs(A[y][x] - A[ny][nx]);
        if (dif >= L && dif <= R) {
            return true;
        }
    }

    return false;
}

void findRes(int i, int j) {
    queue<pair<int, int>> q;
    queue<pair<int, int>> q2;
    int sum = 0, cnt = 0;

    visit[i][j] = true;
    q.push({ i,j });
    q2.push({ i,j });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        sum += A[y][x];
        cnt++;

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

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (visit[ny][nx]) continue;
            
            int dif = abs(A[y][x] - A[ny][nx]);
            if (dif >= L && dif <= R) {
                visit[ny][nx] = true;
                q.push({ ny,nx });
                q2.push({ ny,nx });
            }
        }
    }

    while (!q2.empty()) {
        int y = q2.front().first;
        int x = q2.front().second;

        A[y][x] = sum / cnt;

        q2.pop();
    }
}

void solution() {
    while (check) {
        check = false;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j] && isTrue(i, j)) {
                    findRes(i, j);
                    check = true;
                }
            }
        }

        memset(visit, false, sizeof(visit));
        if(check) res++;
    }

    cout << res;
}

int main() {
    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 >> A[i][j];
        }
    }

    solution();

    return 0;
}