[C++] 16234 인구이동

풀이

문제는 인구이동을 며칠동안 하는지를 묻고있습니다.

그리디한 문제가 아닌
시뮬레이션을 통해 문제를 해결할 수 있었습니다.

국경선 공유하는 인구차이가 L명이상 R명이하라면 1일 동안 국경선을 열게되며,
국경선이 열린 국가는 연합이 됨 (같은 연결요소가 된다고 표현함.)
연합을 이루는 각 칸의 인구수는 총인구/칸수 가 된다.

따라서 하루마다 완전탐색과 DFS를 통해 연결요소를 구하고 해당 연결요소에서 인구를 분배하는 과정을 반복합니다.

해당 반복을 인구이동이 일어나지 않을 때까지 반복하며
이를 day 변수를 통해 카운팅하여 정답을 도출하였습니다.

코드

//
//  main.cpp
//  16234
//
//  Created by 홍승완 on 2024/01/17.
//

#include <bits/stdc++.h>
using namespace std;
int n,r,c,L,R;
int maps[51][51];
int visited[51][51];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<pair<int,int>>tmp;
vector<vector<pair<int,int>>>v;
void dfs(int x, int y){
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<0||yy<0||xx>=n||yy>=n||visited[xx][yy]==1)continue;
        if(abs(maps[x][y]-maps[xx][yy])>=L&&abs(maps[x][y]-maps[xx][yy])<=R){
            tmp.push_back({xx,yy});
            visited[xx][yy]=1;
            dfs(xx, yy);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>L>>R;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>maps[i][j];
        }
    }

    int day=0;
    while(1){
        // 인구이동여부 변수
        bool chk = false;
        
        // init
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)visited[i][j]=0;
        v.clear();
        
        // 연결요소 찾기
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(visited[i][j]==0){
                    tmp.clear();
                    tmp.push_back({i,j});
                    visited[i][j]=1;
                    dfs(i,j);
                    v.push_back(tmp);
                }
            }
        }
        // 여기서 완전탐색을 통해 연결요소들이 v에 모두 저장됨
        
        // 인구이동하면서 변수 토글
        for(auto k:v){
            // 연결요소 개수가 1보다크면 인구이동이 있음.
            if(k.size()>1)chk=true;
            
            int sum=0;
            // sum에 연결요소의 인구합저장
            for(auto elem: k){
                sum+=maps[elem.first][elem.second];
            }
            sum/=k.size(); // 인구평균으로 나눔
            
            // 해당 연결요소들에 인구를 나눔
            for(auto elem: k){
                maps[elem.first][elem.second] = sum;
            }
        }
        
        // 인구이동 없었으면 break
        if(!chk)break;
        day++;
    }
    cout<<day<<"\n";
    
    return 0;
}

결과