[C++,구현] 백준 16234번 인구 이동 문제풀이

문제 링크

백준 16234번 인구 이동

16234번: 인구 이동

 

문제를 풀고 나서 생각해보니 연합을 만들 때 DFS/BFS 어느 방법으로 해도 상관없을것 같다. 나는 DFS를 사용하였다.

side case에 걸리지 않고 한번에 통과해서 기분좋았던 문제였다. ㅎㅎ 

 

#include <iostream>
#include <cmath>
using namespace std;
int N,L,R,ans=0,sum,cnt,pos=1;
int map[51][51],tmap[51][51],visited[51][51],zero[51][51];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
 
void map_copy(int (*a)[51],int (*b)[51]){
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
        a[i][j]=b[i][j];
}
 
void dfs(int x,int y){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||ny<0||nx>N-1||ny>N-1)continue;
            if(abs(map[x][y]-map[nx][ny])>=L&&abs(map[x][y]-map[nx][ny])<=R&&!visited[nx][ny]){
            visited[nx][ny]=pos;dfs(nx,ny);}
        }    
    
}
 
void move(){
    sum=0;cnt=0;
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
        if(visited[i][j]==pos){sum+=map[i][j];cnt++;}
    
    sum/=cnt;
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
        if(visited[i][j]==pos)tmap[i][j]=sum;
        
    pos++;
}
 
void make_union(){
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            for(int i=0;i<4;i++)
                for(int j=0;j<4;j++){
                    int nx=x+dx[i],ny=y+dy[i];
                    if(nx<0||ny<0||nx>N-1||ny>N-1)continue;
                    if(abs(map[x][y]-map[nx][ny])>=L&&abs(map[x][y]-map[nx][ny])<=R&&!visited[x][y]){
                    visited[x][y]=pos;
                    dfs(x,y);
                    move();
                    }
                }
        }
    }
}
 
bool end(){
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            for(int i=0;i<4;i++)
                for(int j=0;j<4;j++){
                    int nx=x+dx[i],ny=y+dy[i];
                    if(nx<0||ny<0||nx>N-1||ny>N-1)continue;
                    if(abs(map[x][y]-map[nx][ny])>=L&&abs(map[x][y]-map[nx][ny])<=R){
                    return true;
                    }
                }        
        }
    }
    return false;
}
 
void solve(){
    map_copy(tmap,map);
    while(end()){
    map_copy(visited,zero);
    make_union();
    map_copy(map,tmap);
    pos=1;ans++;
    }
    cout<<ans;
}
 
main(){
    ios::sync_with_stdio(0);
    cout.tie(NULL);
    cin.tie(NULL);
    cin>>N>>L>>R;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>map[i][j];
    
    solve();
}

 

입력을 받은 후에 함수를 5개 만들었다.

• map의 상태를 초기화 시켜주거나 복사해주는 map_copy함수
• 현재의 map의 인구상태를 기준으로 연합을 만드는 make_union함수
• 연합을 만들 때 사용하는 dfs함수
• 연합을 만들고 이동한 후의 상태를 나타내는 move함수 

여기서 주의할 부분이 이동한 후의 상태는 map에 넣지 않고 tmap에 넣었다.

왜냐하면 인구는 현재 상태를 기준으로 모든 연합이 동시에 이동하기 때문이다. 

개별적으로 이동하면 연합을 다시 만들때 영향이 미쳐 오류가 발생한다.

• 종료할 조건인지 판별하는 end 함수를 만들어 while문이 빠져나온다면 정답을 출력하게 하였다.

pos 변수는 각 연합을 구분짓게 해 dfs를 할 경우 방문체크의 역할도 담당한다.