16234. 인구이동

삼성 SW역량 테스트 기출문제.

 

BFS를 사용하는 완전탐색 문제이자,

주어진 규칙을 잘 구현하는 시뮬레이션 문제이다.

 

문제 그대로만 하면 된다.

BFS의 결과로 최소 신장트리(Minimum spanning tree)가 나오는데, 그 트리가 바로 하나의 연합이다.

처음에 문제를 보고, 하루에 연합이 2개이면 인구이동도 2번인가 했었는데 아니었다.

하루에 인구이동이 일어났으면 연합의 개수에 상관없이 그냥 인구이동이 한번 추가 되는 것이다.

 

무튼, 연합이 만들어지면, 그 node들을 하나의 vector에 저장해놓고, 인구이동값을 각 node에 대입해주면 된다.

그래서 코드는 크게

bfs()와 immigrate()로 나뉜다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N, L, R;
int a[50][50];
bool visited[50][50];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int ans;

struct Country{
    int x, y;
};
vector<Country> union_;
int unionSum;

void bfs(int start_x, int start_y){
    queue<Country> q;
    q.push({start_x, start_y});
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        union_.push_back({x, y});
        unionSum += a[x][y];
        q.pop();
        for (int i=0; i<4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            int dif = abs(a[nx][ny] - a[x][y]);
            if (0 <= nx && nx < N && 0 <= ny && ny < N && visited[nx][ny] == false
                && L <= dif && dif <= R){
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

void immigrate(){
    int one = unionSum / (int)union_.size();
    for (int i=0; i<union_.size(); ++i){
        a[union_[i].x][union_[i].y] = one;
    }
}

void initVisited(){
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            visited[i][j] = false;
        }
    }
}

void printA(){
    puts("");
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            printf("%d ", a[i][j]);
        }
        puts("");
    }
}

int main() {
    scanf("%d %d %d", &N, &L, &R);
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            scanf("%d", &a[i][j]);
        }
    }

    while(true){
        int cnt = 0;
        for (int i=0; i<N; ++i){
            for (int j=0; j<N; ++j){
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    unionSum = 0;
                    bfs(i, j);
                    if (union_.size() > 1){
                        ++cnt;
                        immigrate();
                    }
                    union_.clear();
                }
            }
        }
        if (cnt == 0) break;
        ++ans;
        
        initVisited();
    }
    printf("%d\n", ans);
    return 0;
}