[브루트 포스 / BOJ 16234 / C++] 인구 이동

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

16234번: 인구 이동

1) while(1)을 통해 계속해서 인구 이동을 체크하는 로직을 생각한다. 만약 인구이동이 발생됐다면, day++가 되고 그게 아니라면 종료하고 즉시 day를 출력한다.
2)모든 칸에 대한 인구이동을 dfs로 확인한다.
3)발생한 인구이동에 대한 연합의 인구수와 연합들의 위치를 저장하여, 평균을 구해 인구수를 맞춘다. 이때, 연합이 단 한개라면, 그 즉시 while문을 종료한다.

뭔가 쉬운듯 복잡....

우선 dfs나 bfs로 로직을 짜는 건 어렵지 않았을 것이다. 상하좌우와 차이를 구해서 그 차이가 L과 R 이내면 그즉시 연합으로 표시하면 된다. 이런식으로 연합을 늘려나간다.

 

모든 연합이 가능한 경우를 확인했다면, 그 연합들의 평균을 구한다. 그리고 그 연합들을 평균값으로 갱신해준다.

 

그런데, 연합을 이루는 국가가 단 한개라면, 그건 인구이동이 발생하지 않는 다는 것을 의미하므로 프로그램을 종료한다!

 

이 문제의 핵심은 도대체 어디에서 인구이동이 발생하지 않았다고 표시하고, 종료해줄까를 생각하는 것이 중요한 것 같다..!! 안그러면 헤맨다. 간단하게 while - flag 형식을 써주자..!

 

#include <bits/stdc++.h>

using namespace std;

int N, L, R, res;
int bd[54][54], vis[54][54];

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

int unions;
vector<pair<int,int>> uni_p;

void dfs(int y, int x){
    

   for(int i = 0 ; i < 4 ; i++){
       int ny = y + dy[i];
       int nx = x + dx[i];
       
       if(ny >= N || nx >= N || ny < 0 || nx < 0) continue;
       if(vis[ny][nx]) continue;
       
       int diff = abs(bd[ny][nx] - bd[y][x]);
       
       if(diff >= L && diff <= R){
           unions += bd[ny][nx];
           uni_p.push_back({ny,nx});
           vis[ny][nx]=1;
           dfs(ny, nx);
       }
       
   }
    
}

int main(){
    ios::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 >> bd[i][j];
        }
    }
    
    while (true) {
        
        
        int flag = 0;
        
        memset(vis, 0, sizeof(vis));
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                if(!vis[i][j]){ // 해당좌표가 union이고 아직 방문안했으면 union연합시키기.
                    
                    
                    if(uni_p.size()) uni_p.clear();
                    uni_p.push_back({i, j});
                    unions=bd[i][j];
                    vis[i][j] = 1;
                    dfs(i,j);
                    
                    if(uni_p.size()==1) {continue;} // uni할게 없으면 인구 이동 없음.
                    int avg = unions / uni_p.size();
                    
                    for(auto k : uni_p){
                        bd[k.first][k.second] = avg;
                        flag=1;
                    } // 연합 숫자 맞춰주기. 인구이동발생!
                    
                }
            }
        }
        
        if(!flag) break; // 인구이동 발생 없을시 중단.
        res++;
        
      
    }
    
    
    
    cout << res;
    
}