[백준/BOJ] 16234번 인구 이동 (C++)

www.acmicpc.net/problem/16234

16234번: 인구 이동

삼성 역량 테스트 기출 문제 : BFS + 시뮬레이션(구현) (다시 풀기)

문제의 포인트는 BFS 탐색시에 방문하는 좌표를 저장할 큐를 하나 더 선언하는 것입니다. 그래서 BFS를 탐색과 좌표 저장을 동시에 진행하면서, 좌표를 저장한 큐를 하나씩 꺼내어 이에 평균을 넣어주면 쉽게 해결할 수 있습니다.

 

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

int N, L, R, answer;
int map[51][51];
bool visit[51][51], flag = true;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(int sx, int sy) {
    queue<pair<int, int > > q, u; // BFS 탐색을 위한 큐, 방문 기록(좌표)를 저장하기 위한 큐
    q.push({ sx, sy });
    u.push({ sx, sy });
    visit[sx][sy] = true;
    int sum = map[sx][sy];
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int diff = abs(map[x][y] - map[nx][ny]);
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(visit[nx][ny] || diff < L || diff > R) continue;
            
            q.push({ nx, ny });
            u.push({ nx, ny });
            visit[nx][ny] = true;
            sum += map[nx][ny];
            flag = true;
        }
    }
    
    int avg = sum / u.size(); // 인구 이동의 평균
    while(!u.empty()) {
        map[u.front().first][u.front().second] = avg;
        u.pop();
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> L >> R;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    
    while(flag) {
        flag = false;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(!visit[i][j]) BFS(i, j);
            }
        }
        memset(visit, false, sizeof(visit));
        answer++;
    }
    
    cout << answer - 1;
}