백준 16345번 - 인구 이동

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

16234번: 인구 이동

 

• 문제 해결 방법

BFS를 이용한 시뮬레이션 구현문제입니다. 모든 인접한 나라와 나라사이에 국경선이 열려있는지, 즉 인접한 나라로 이동할 수 있는지 확인한 다음, 만약 이동할 수 있다면 그 나라를 시작점으로 하여 BFS를 수행하고 인구이동 결과를 업데이트 합니다. 이때 방문처리도 같이 해주어야 합니다.

 

노드마다 이동할 수 있는지 확인하는 코드가 chkAlly 함수에 구현되어 있고 시작점으로 부터 BFS를 수행하는 코드가 solve에 구현되어 있습니다.

 

chkAlly 함수로 이동할 수 있는지 확인할때 아래코드와 같이 매번 모두 탐색해도 되지만 더 빠르게 수행하기 위해 큐를 한개 더 사용하여 chkAlly를 수행했습니다. (전체 코드에서 queue<pii> sq)

c++

닫기 줄바꿈

​​​​int ans = 0;
​​​​bool chk = true;
​​​​while(chk){
​​​​​​​​chk = false;
​​​​​​​​memset(vi,0,sizeof(vi));
​​​​​​​​for(int i=0; i<N; i++){
​​​​​​​​​​​​for(int j=0; j<N; j++){
​​​​​​​​​​​​​​​​if(chkAlly(i,j)){
​​​​​​​​​​​​​​​​​​​​bfs(i,j);
​​​​​​​​​​​​​​​​​​​​chk = true;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(chk) ans++;
​​​​}
​​​​cout<<ans;

 

인구가 한번 이동한 후에 그 다음으로 인구가 이동할 수 있는 나라들을 탐색해야 한다면, 그 시작점은 반드시 이전의 이동으로 인해 인구수가 바뀐 나라부터 시작되므로 해당 나라만 큐에 넣어 탐색해주면 수행시간을 줄일 수 있습니다.

 

 

 

• C++ 전체 코드

c++

닫기 줄바꿈

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using tpi = tuple<int,int,int>;
const int INF = 0x3f3f3f3f;

int N,L,R;
int m[51][51]{};
queue<pii> sq;
bool vi[51][51]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

void solve(int sty, int stx){
​​​​vector<pii> v;
​​​​queue<pii> q;
​​​​v.push_back({sty,stx});
​​​​q.push({sty,stx});
​​​​vi[sty][stx] = true;
​​​​int sum = m[sty][stx];
​​​​
​​​​while(!q.empty()){
​​​​​​​​int cy = q.front().xx;
​​​​​​​​int cx = q.front().yy;
​​​​​​​​q.pop();

​​​​​​​​for(int i=0; i<4; i++){
​​​​​​​​​​​​int ny = cy + dy[i];
​​​​​​​​​​​​int nx = cx + dx[i];
​​​​​​​​​​​​if(ny<0 || nx<0 || ny>=N || nx>=N || vi[ny][nx]) continue;
​​​​​​​​​​​​int diff = abs(m[cy][cx] - m[ny][nx]);
​​​​​​​​​​​​if(diff>=L && diff<=R) {
​​​​​​​​​​​​​​​​v.push_back({ny,nx});
​​​​​​​​​​​​​​​​q.push({ny,nx});
​​​​​​​​​​​​​​​​vi[ny][nx] = true;
​​​​​​​​​​​​​​​​sum += m[ny][nx];
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​int res = sum / v.size();
​​​​for(auto cord : v){
​​​​​​​​int y = cord.xx;
​​​​​​​​int x = cord.yy;
​​​​​​​​m[y][x] = res;
​​​​​​​​sq.push({y,x});
​​​​}
}

bool chkAlly(int cy, int cx){
​​​​if(vi[cy][cx]) return false;
​​​​for(int i=0; i<4; i++){
​​​​​​​​int ny = cy + dy[i];
​​​​​​​​int nx = cx + dx[i];
​​​​​​​​if(ny<0 || nx<0 || ny>=N || nx>=N) continue;
​​​​​​​​int diff = abs(m[cy][cx] - m[ny][nx]);
​​​​​​​​if(diff>=L && diff<=R) return true;
​​​​}
​​​​return false;
}

int main() {
​​​​ios_base::sync_with_stdio(0);
​​​​cin.tie(0);
​​​​cin>>N>>L>>R;
​​​​for(int i=0; i<N; i++){
​​​​​​​​for(int j=0; j<N; j++){
​​​​​​​​​​​​cin>>m[i][j];
​​​​​​​​​​​​sq.push({i,j});
​​​​​​​​}
​​​​}
​​​​
​​​​int ans = 0;
​​​​bool chk = true;
​​​​while(chk){
​​​​​​​​chk = false;
​​​​​​​​memset(vi,0,sizeof(vi));
​​​​​​​​
​​​​​​​​// 현재 sq에 저장된 나라의 수 만큼만 chkAlly를 수행해야 함에 주의
​​​​​​​​int sz = sq.size();
​​​​​​​​for(int i=0; i<sz; i++){
​​​​​​​​​​​​int cy = sq.front().xx;
​​​​​​​​​​​​int cx = sq.front().yy;
​​​​​​​​​​​​sq.pop();
​​​​​​​​​​​​if(chkAlly(cy,cx)){
​​​​​​​​​​​​​​​​solve(cy,cx);
​​​​​​​​​​​​​​​​chk = true;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(chk) ans++;
​​​​}
​​​​cout<<ans;
}