백준 문제 16234번 인구이동 문제풀이 c++

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

16234번: 인구 이동

 

문제해석

 

dfs를 사용해서 구현하였다.

아이디어는 이렇다.

1.인접한 나라의 인구 차이가 범위내에 있다면 벡터를 인접리스트처럼 사용해서 국경을 연결해 그래프를 만든다.

2.그리고 dfs를 통해서 연결된 모든 국가의 인구를 합쳐서 국가의 개수만큼으로 나누어 재분배를 시킨다.

1,2를 반복하고 종료 조건은 9328번 열쇠 코드에서 작성했던거 처럼 전과 후의 배열을 비교해서 인구가 달라진 점이 없는 경우 종료를 한다.

한 국가라도 인구가 변하였다면 다시 1번으로 돌아가서 반복한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
void dfs(int x);
void setting();
bool inside(int ny,int nx);
vector <int> v[2500];
vector <pair<int,int>> u;
bool visited[2500];
int a[50][50];
int before[50][50];
int n,l,r,sum,depth;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>l>>r;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
    while(1)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                before[i][j]=a[i][j];
            }
        }
        setting();
        for(int i=0; i<n*n; i++)
        {
            sum=0; depth=0; u.clear();
            dfs(i);
            for(int j=0; j<u.size(); j++)
            {
                int row=u[j].first;
                int col=u[j].second;
                a[row][col]=sum/depth;
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(before[i][j]!=a[i][j])
                {
                    goto Label;
                }
            }
        }
        break;

        Label: 
        ans++;
    }
    cout<<ans;
}
void dfs(int x){
    if(visited[x]==1)
    {
        return;
    }
    visited[x]=1;
    depth++;
    int row=x/n;
    int col=x%n;
    sum=sum+a[row][col];
    u.push_back({row,col});
    for(int i=0; i<v[x].size(); i++)
    {
        dfs(v[x][i]);
    }
}
void setting(){
    sum=0; depth=0;
    u.clear();
    for(int i=0; i<2500; i++)
    {
        visited[i]=0;
        v[i].clear();
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            int d;
            if(inside(i,j+1))
            {
                d=abs(a[i][j]-a[i][j+1]);
                if(l<=d&&d<=r)
                {
                    v[i*n+j].push_back(i*n+j+1);
                    v[i*n+j+1].push_back(i*n+j);
                }
            }
            if(inside(i+1,j))
            {
                d=abs(a[i][j]-a[i+1][j]);
                if(l<=d&&d<=r)
                {
                    v[i*n+j].push_back((i+1)*n+j);
                    v[(i+1)*n+j].push_back(i*n+j);
                }
            }
        }
    }
}
bool inside(int ny,int nx){
    if(0<=ny&&ny<n&&0<=nx&&nx<n)
    {
        return true;
    }
    else
    {
        return false;
    }
}