[ BOJ / C++ ] 16234번 : 인구 이동

[ BOJ ] 16234번 : 인구 이동

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

16234번: 인구 이동

---

[  문제  ]

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

 

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

[  입력  ]

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

[  출력  ]

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

---

[  문제 접근 및 풀이  ]

이 문제는 크게 두 단계로 나눌 수 있다.

1. 연합 확인

2. 연합마다 인구수 통합

\(N\)×\(N\)의 각 칸마다 주변과 연합이 되는지 각 칸마다 BFS를 돌려주면서

주변 4방향의 칸이 L명 이상, R명 이하면 해당 칸과 연합으로 간주하면서 Vector에 넣어준다.

또한 연합의 인구수는 sum이라는 변수에 넣어두면서 각 칸의 연합을 확인 후 연합이 있는 경우

Vector에 있는 연합들의 인구수를 sum을 연합의 수로 나눈 값으로 업데이트 해주었다.

또한 연합이 있어 인구수가 업데이트 되었다면 하루를 추가한다.

그렇지 않다면 인구 이동이 완료되었다고 판단하고 반복문을 종료한다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
int N,L,R,sum,Day,A[51][51],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool vis[51][51],check;
queue<pair<int,int>> q;
vector<pair<int,int>> V; //연합 인구 이동 인원 저장
void input();
void solve();
void bfs(int I,int J); //연합 확인 
void move(); //인구 이동
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	input();
	solve();
} 
void input(){
    cin >> N >> L >> R;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) cin>>A[i][j];
    }
}
void solve(){
    while(true){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++) {
                sum=0; //연합의 인구수 확인
                if(!vis[i][j]) bfs(i,j);
                if(check) move(); //연합이 있다면 인구 이동 시작
                else V.clear(); //연합이 없으면 Vector 초기화
            }
        }
        if(!check)break; //연합 인구 이동이 없으면 종료
        Day++; //하루 추가
        memset(vis,false,sizeof(vis));
        check=false; //하루 동안 연합이 존재하는지 확인
    }
    cout<< Day;
}
void bfs(int I,int J){ //A[I][J]에 대한 연합 칸 수 확인
    q.push({I,J});
    V.push_back({I,J});
    vis[I][J]=true;
    sum+=A[I][J];
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(int dir=0;dir<4;dir++){
            int nx=cur.x+dx[dir],ny=cur.y+dy[dir];
            if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
            if(vis[nx][ny]) continue;
            if(abs(A[nx][ny]-A[cur.x][cur.y])<L || abs(A[nx][ny]-A[cur.x][cur.y])>R) continue;
            V.push_back({nx,ny}); //연합 인구 이동 저장
            sum+=A[nx][ny];
            vis[nx][ny]=true;
            q.push({nx,ny});
            check=true;
        }
    }
}
void move(){ //인구 이동
    if(V.size()) sum/=V.size(); 
    while(!V.empty()){
        auto cur=V.back();
        V.pop_back();
        A[cur.x][cur.y]=sum;
    }
}

---