[백준 16234번] 인구 이동

문제 링크: https://www.acmicpc.net/problem/16234

16234번: 인구 이동

<문제 풀이> BFS

 

BFS를 이용해서 두 인구 차이가 L 이상 R 이하를 만족하는 연결 요소를 구하면 되는데, 이때 지나온 좌표, 현재까지 인구의 합을 저장해 두고 queue가 비면 인구 이동을 진행하면 된다. 

 

현재까지의 좌표의 개수가 2개 이상일 때 두 그룹 이상이 생기는 거니깐 이 경우에만 인구 이동을 진행한다.

-> bfs가 bool을 return 하도록 하고 인구 이동이 한 번 이상 진행한 경우  true

-> bfs가 true면 다시 bfs를 호출  

 

<C++ 소스 코드>

#include<iostream>
#include<utility>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
 
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
int N, L, R;
int A[50][50];
bool visited[50][50];
bool bfs() {
    bool ret = false;
    fill(&visited[0][0], &visited[49][50], 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j]) continue;
            queue<pair<int, int > > Q;
            vector<pair<int, int> > trace;
            int tot = A[i][j];
            Q.push({ i, j });
            trace.push_back({ i, j }); //지나온 좌표 저장
            visited[i][j] = true;
            while (!Q.empty()) {
                auto cur = Q.front(); Q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
                    if (visited[nx][ny])continue;
                    if (A[nx][ny] == -1)continue;
                    int diff = abs(A[nx][ny] - A[cur.X][cur.Y]);
                    if (diff< L || diff > R) continue;
                    tot += A[nx][ny]; // 인구이동이 가능하면
                    Q.push({ nx, ny });
                    visited[nx][ny] = true;
                    trace.push_back({ nx, ny });
 
                }
            }
            int trace_size = trace.size();
            if (trace_size >= 2) {
                ret = true;
                for (auto& e : trace) {
                    A[e.X][e.Y] = tot / trace_size;
                }
            }
        }
    }
 
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> L >> R;
    fill(&A[0][0], &A[49][50], -1);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin>>A[i][j];
        }
    }
    int ans = 0;
    while (bfs()) {
        ans++;
    }
    cout << ans;
    return 0;
}