백준 16234번 - 인구 이동

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

현재 좌표를 기준으로 주변 좌표의 값의 차이가

L이상 R이하일 때 국경선을 열어 연합을 통해 인구 이동을 진행해주면 된다.

문제를 보고 주변 좌표의 차이값을 탐색해야 된다는 것을 확인한 후에 DFS 방식으로 연합을 이루고 있는 좌표를 포함시켰다.

접근 방향은 다음과 같다.

1) 현재의 좌표를 이전에 방문하지 않았다면 인구 이동 좌표(pos)에 포함시킨 후 DFS를 실행한다.

2) DFS 함수를 통해 주변 4방향을 모두 탐색한 후, 차이값이 제한 조건을 만족할 때, 인구 이동 좌표(pos)에 포함시킨다.

3) 2번 과정을 반복 한 후, 인구 이동 좌표(pos)가 1개 보다 많을 때 인구 수를 칸의 개수에 맞게 모두 업데이트 해준다.

    (만약 인구 이동 좌표가 초기 좌표 1개라면 다시 1번으로 돌아간다)

4) 한 번도 인구 이동이 이루어지지 않았다면 종료해준다.

문제를 풀면서 차이 값 확인을 어떻게 할까 고민을 했는데

현재 좌표를 먼저 포함을 해주고, 인구 이동 좌표가 1보다 클 때를 기점으로 인구 이동이 일어날 수 있도록 했다.

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int N,L,R;
 
int sum=0; //연합 인구 수
int ans=0;
vector<pair<int,int>> pos; //연합을 이루고 있는 좌표
vector<vector<int>> A; //각 나라의 인구 수
vector<vector<int>> visited; //방문 여부
 
void dfs(int y,int x){
    
    for(int dir=0;dir<4;dir++){
        
        int ny=y+dy[dir];
        int nx=x+dx[dir];
        
        if(ny<0 || ny>=N || nx<0 ||nx>=N)
            continue;
        
        if(visited[ny][nx]!=0)
            continue;
        
        int value=(int)abs(A[y][x]-A[ny][nx]);
        if(value<L || value>R)
            continue;
        
        sum+=A[ny][nx];
        visited[ny][nx]++;
        pos.push_back(make_pair(ny,nx));
        dfs(ny,nx);
    }
}
int main(){
    
    cin>>N>>L>>R;
    A=vector<vector<int>> (N,vector<int>(N,0));
    
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&A[i][j]);
    
    
    while(true){
        int move_cnt=0;
        visited=vector<vector<int>> (N,vector<int>(N,0));
        
        for(int y=0;y<N;y++){
            for(int x=0;x<N;x++){
                
                if(visited[y][x]!=0)
                    continue;
                
                sum=A[y][x]; //초기 값(연합 인구 수)
                visited[y][x]++; //y,x 방문
                
                pos.clear();
                pos.push_back(make_pair(y,x));
                dfs(y,x);
                
                if(pos.size()==1) //국경선 모두 닫혀있을 때
                    continue;
 
                move_cnt++; //인구 이동
                sum/=pos.size();
                for(int i=0;i<pos.size();i++)
                    A[pos[i].first][pos[i].second]=sum;
 
            }
        }
        
        if(move_cnt==0) //인구 이동 한 번도 없을 때
            break;
        
        ans++;
    }
    
    cout<<ans<<endl;
    
    return 0;
}