백준 16345번 - 인구 이동

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

16234번: 인구 이동

 

• 문제 해결 방법

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

 

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

 

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

    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++ 전체 코드

#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;
}