백준 16234. 인구이동 (bfs, 구현)

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

16234번: 인구 이동

bfs를 이용한 구현 문제이다. 

문제 아이디어는 다음과 같다

for(i = n) for(j = n) a[i][j]에서 bfs를 돌면서 연합을 이루는 나라를 찾고, 그 연합나라의 인구 재배치를 한다. 

그리고 이것을 인원이 재배치 할 일이 없을 때 까지 반복한다(while)

 

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int n, l, r;
int a[52][52];
int dx[4] = {-1, 0, 1, 0}; //위 오른쪽 아래 왼쪽
int dy[4] = {0, 1, 0, -1};
int v[52][52];//방문 표시
queue<pair<int, int>> _queue; 
queue<pair<int, int>> _tmp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l >> r;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    

    int area = 0;
    int ans = 0;
    int sum;
    int num;

    while(true)
    {
        
        area = 0;
        //v초기화
        for(int i = 0; i < n; i++)
        {
            fill(v[i], v[i] + n, 0);
        }
        for(int i = 0; i < n; i++)  
        {
            for(int j = 0; j < n; j++)
            {
                if(v[i][j] == 0) // 방문안했으면
                {
  
                    sum = a[i][j];
                    num = 1;
                    _queue.push(make_pair(i, j));
                    _tmp.push(make_pair(i, j));
                    v[i][j] = 1;
                    area+=1;

                    while(!_queue.empty())
                    {
                        int curx = _queue.front().first;
                        int cury = _queue.front().second;
                        _queue.pop();

                        for(int dir = 0; dir < 4; dir++)
                        {
                            int nx = curx + dx[dir];
                            int ny = cury + dy[dir];

                            if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1) continue;
                            if(v[nx][ny] != 0) continue;
                            if(abs(a[curx][cury] - a[nx][ny]) >= l && abs(a[curx][cury] - a[nx][ny]) <= r )
                            {
                                _queue.push(make_pair(nx, ny));
                                _tmp.push(make_pair(nx, ny));
                                v[nx][ny] = 1; 
                                sum+=a[nx][ny];
                                num+=1;

                            }
                            

                        }
                    }
                }
                int valu = sum / num;

                while(!_tmp.empty()) // 이번 순회에서 연합이었던 좌표들에 인구수(valu)를 지정함.
                {
                    int curx = _tmp.front().first;
                    int cury = _tmp.front().second;
                    _tmp.pop();

                    a[curx][cury] = valu; 

                }
            }
        }

        if(area == n*n) break;
        ans+=1;

    }

    cout << ans;


    

    


    

   
}