[bfs] 백준 16234 인구 이동

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

삼성 SW 역량 테스트 기출 문제 라는 문제집에 있는 문제입니다.

이 문제도 생각보다 많이 쉬웠습니다. 

우선 map에 있는 연합을 하나 찾고, 그 연합의 값을 전부 바꿉니다. 이때, visited가 큰 역할을 합니다. 바꾼 연합을 또 바꾸는 일이 사라지거든요. 이 과정을 계속 반복하니 풀렸습니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int map[50][50];
    int N,L,R;
    bool chk = true;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    int ans = 0;
    queue<pair<int,int>> q;      //bfs용
    queue<pair<int,int>> pos; //연합의 좌표를 저장
    
    cin >> N >> L >> R;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++)
            cin >> map[i][j];
    }
    
    while(chk){
        bool visited[50][50] = {};
        chk = false; ans+=1;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(visited[i][j]) continue;
                int sum = map[i][j];
                q.push({j,i});
                pos.push({j,i});
                visited[i][j] = 1;
                
                while(!q.empty()){
                    int x_tmp = q.front().first;
                    int y_tmp = q.front().second;
                    q.pop();
                    
                    for(int k = 0; k < 4; k++){
                        int x = x_tmp+dx[k];
                        int y = y_tmp+dy[k];
                        if(x < 0 || y < 0 || x >= N || y >= N || visited[y][x] || abs(map[y_tmp][x_tmp]-map[y][x]) < L ||abs(map[y_tmp][x_tmp]-map[y][x])>R)
                            continue;
                        chk = true;
                        q.push({x,y});
                        pos.push({x,y});
                        sum+=map[y][x];
                        visited[y][x] = 1;
                    }
                
                }
            
                
                int avr = sum/pos.size();
 
                while(!pos.empty()){
                    map[pos.front().second][pos.front().first] = avr;
                    pos.pop();
                }
            }
        }
        
    }
    cout << ans-1;
}