[백준 16234][C++] 인구 이동(Gold 5)

[문제 보기]

 16234. 인구이동

16234번: 인구 이동

 

[풀이과정]

bfs()를 이용해서 문제를 풀었다. 전체적인 풀이 방법은 bfs()를 이용하여 연합이 될 수 있는 국가들을 찾고 인구 이동을 

시켜준다. 이렇게 얘기하면 쉬운 문제일 듯싶으나, 여러 조건들이 존재를 하여 조건문을 잘 맞춰줘야 문제를 풀 수 있다.

 

main()

while()문을 통해 인구 이동이 없을 때까지 반복문을 돌려주는데 멈추게 해주는 역할로 flag를 주었다.

check[][] 2차원 배열을 통해 각 연합을 판별해준다. 그리고 map을 전체적으로 검사를 진행할 때 연합이 여러 개가

나올 수 있기 때문에 group 변수를 사용하여 각 연합를 구별해주었다. 

map을 이중 for문을 통해 검사를 해주는데, 이 부분에서 moving에 각 좌표를 push 해주고 bfs()을 실행해준다. 

bfs()를 실행 후 check[i][j] 값이 0이면(연합이 없다는 뜻) -1로 바꿔준다. (-1은 방문했지만 연합이 없다는 의미 ->

중복 계산을 없애주기 위함)

전체적으로 확인을 하고 flag가 true값이면 인구 이동이 적어도 한번은 했다는 뜻이므로 ans를 하나 증가해준다.

 

flag -> 인구 이동이 한번이라고 일어나면 true값을 가지게 되어 while() 문을 실행하고, 인구 이동이 일어나지 않으면 

           while()문은 끝난다.

group -> 각 연합에 대한 데이터를 가지고 있는 변수로, bfs()가 실행이 되어 연합이 되면 같은 group 값을 가지게 된다.

 

bfs(int group)

cnt는 연합 갯수를 의미하는데 while() 문을 실행 후 cnt가 1이면 연합이 없다는 의미로 인구의 변화가 없기 때문에 바로

return을 해준다.

people 변수는 연합의 전체 인구를 의미하고 while()을 실행하면서 연합으로 추가되는 국가의 인구가 더해질 예정이다. 

 

탐색을 통해 연합을 찾고 각 연합의 수와 연합의 전체 인구수를 통해 인구를 변화시켜준다. 이 부부에서 group 사용

 

[소스코드]

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
int n, l, r, ans = 0;
bool flag = true;
int map[50][50] = {0};
queue<pair<int, int>> moving;
int check[50][50];
pair<int, int> dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void all_printf(){
    cout << "\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

void bfs(int group){
    int cnt = 1;
    int people = map[moving.front().first][moving.front().second];

    while(!moving.empty()){
        int y = moving.front().first;
        int x = moving.front().second;
        check[y][x] = group;
        moving.pop();

        for(int i=0; i<4; i++){
            int nexty = y + dir[i].first;
            int nextx = x + dir[i].second;

            if(nexty <0 || n <= nexty || nextx < 0 || n <= nextx)
                continue;
            if(check[nexty][nextx] == 0){
                int sub = abs(map[y][x] - map[nexty][nextx]);
                if( l <= sub && sub <= r){
                    check[nexty][nextx] = group;
                    moving.push({nexty, nextx});
                    people += map[nexty][nextx];
                    cnt++;
                }
            }
        }
    }

    if(cnt == 1){
        return;
    }

    int change = people/cnt;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(check[i][j] == group)
                map[i][j] = change;
        }
    }
    flag = true;
}

int main(){
    cin >> n >> l >> r;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    while(flag){
        memset(check, 0, sizeof(check));
        flag = false;
        int group = 1;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(check[i][j] == 0){
                    moving.push({i, j});
                    bfs(group++);
                    if(check[i][j]){
                        check[i][j] = -1;
                    }
                }
            }
        }

        if(flag){
            ans++;
        }
        //all_printf();
    }

    cout << ans ;
}

 

[해결 과정 중 실수한 부분]

bfs를 사용하여 문제를 풀어야 된다고 감은 왔는데, 뭔가 아닌것도 같아서 다른 방법이 있나 생각하느라 처음

시작하는데 시간이 걸렸다. 그리고 문제를 풀면서 디버깅을 하는 과정에서 빼먹은 조건들이 많아 이를 고치면서

디버깅을 하는데 시간을 많이 잡아먹었다. 

 

하지만 오랜만에 블로그를 안보고 혼자 문제를 풀었던 문제이기 때문에 기분은 너무 좋았다.