[백준,c++] 16234번 - 인구 이동

문제

16234번: 인구 이동

 

코드

#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;

int N,L,R, day;
int map[51][51];
int line[51][51];
bool visited[51][51];

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

bool line_check(){
    bool flag = false;
    for(int i=0; i<N; i++){ // 가로 확인
        for(int k=0; k<N-1; k++){
            int diff = abs(map[i][k] - map[i][k+1]);
            if(diff>=L && diff<=R){ // 인구 차이가 L명이상, R명 이하일 때
                flag = true;
                line[i][k] = 1;
                line[i][k+1] = 1;
            }
        }
    }
    
    for(int k=0; k<N; k++){ // 세로 확인
        for(int i=0; i<N-1; i++){
            int diff = abs(map[i][k] - map[i+1][k]);
            if(diff>=L && diff<=R){ // 인구 차이가 L명이상, R명 이하일 때
                flag = true;
                line[i][k] = 1;
                line[i+1][k] = 1;
            }
        }
    }
    
    return flag;
}


void search_union(int x, int y){ // 연합 탐색
    int peo_sum = map[x][y];
    int blank_cnt = 1;
    visited[x][y] = 1;
    queue<pair<int,int>> q;
    vector<pair<int,int>> coor = {{x, y}};
    q.push({x,y});
    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];
            if(nx>=0 && nx<N && ny>=0 && ny<N){
                int diff = abs(map[x][y] - map[nx][ny]);
                if(!visited[nx][ny] && diff>=L && diff<=R){
                    visited[nx][ny] = 1;
                    q.push({nx, ny});
                    blank_cnt++;
                    peo_sum += map[nx][ny];
                    coor.push_back({nx, ny});
                }
            }
        }
    }
    
    int population = peo_sum / blank_cnt;   // 각 칸을 이룰 새로운 인구 수
    for(auto it: coor) map[it.first][it.second] = population;   //인구 이동
    
}

void move(){
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(line[i][k] && !visited[i][k]) search_union(i, k);
        }
    }
}


void simulation(){
    
    while(line_check()){
        move();
        day++;
        memset(visited, 0 ,sizeof(visited));
        memset(line, 0, sizeof(line));
    }
    
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>L>>R;
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>map[i][k];
        }
    }
    simulation();
    cout<<day;
}

 

풀이

나라의 인구 수

위와 같은 초기의 각 나라와 인구수가 주어졌을 때 각 인접한 나라의 인구수 차이가 L 이상 R이하일 때 아래와 같이 국경선을 오픈할 수 있습니다.

국경선을 해제

오픈된 각 나라의 한 뭉텅이를 연합이라고 칭하며, 연합은 여러 개가 생성될 수 있습니다.

각 연합의 나라의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 로 인구이동이 즉, 인구를 변경시킵니다.

1. 먼저 연합에 상관없이 각 인접한 나라의 인구수 차이가 L 이상 R이하인 모든 나라들을 체크 배열을 통해 기록했습니다.
2. 다음에 체크 배열에 기록된 나라를 반복문을 돌리고, 그 안에서 bfs를 돌려서 연합의 인구수를 갱신했습니다.
3. bfs에서 상하좌우 탐색을 하며 인구수 차이가 L 이상 R이하인 나라만 찾아서 인구수를 갱신하기에, 처음 bfs를 돌릴 때의 나라가 속한 연합 인구수를 갱신할 수 있습니다.
4. 하루를 지나가기에 일수를 +1 해줍니다.
5. 연합을 해제하고, 모든 국경선을 닫습니다.
6. 위 1~5 과정을 연합이 생길때까지 반복합니다.