[백준 16234][C++] 인구 이동

문제

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

16234번: 인구 이동

 

풀이 과정

1. 연합의 개수는 2개 이상일 수 있다. 즉 각 연합별로 인구의 평균을 적용하기 위한 방법을 이용해야 한다.

2. 첫 칸을 너비 우선 탐색 방식 (BFS)으로 탐색하며 각 칸에서 진행할 수 있는 최대의 연합을 구성한다.

    이때 방문되었던 칸은 visited 배열을 통해 기록한다.

    방문되지 않았던 칸에서 다시 BFS를 진행한다.

3. 모든 칸에 대한 연합 정보를 구한다.

4. 연합 정보를 통해 연합끼리 인구의 평균으로 새롭게 업데이트한다.

5. 2번에서 4번 과정을 반복하며 인구의 추가적인 변화가 없을 때까지 진행한다.

6. 인구 이동이 발생한 횟수를 반환한다.

 

 

세부 풀이

(1)

연합의 모양이 아래와 같이 발생할 수 있다. 문제의 [예제 입력 5]의 경우를 보자.

 

[입력]

4 10 50
10 100 20 90
80 100 60 70
70  20  30 40
50 20 100 10

 

위와 같은 입력이 주어졌을 때 다음과 같이 연합이 형성된다. 인구의 차이가 10 이상 50 이하인 인접한 국가끼리 묶인 모습이다.

 

[첫 인구 이동 연합]

1 2 3 3
3 3 3 3
3 3 3 3
3 3 4 3

 

이렇게 인구의 연합은 2개 이상이 충분히 될 수 있다. 따라서 연합 정보를 인구수를 저장한 배열과 동일한 크기의 배열에 저장하고 이용할 수 있도록 구현했다.

 

 

(2)

union_map을 작성하는 make_union 함수는 너비 우선 탐색 방식을 적용했다. 각 칸의 방문 여부를 기록하기 위해 visited 배열을 이용했다.

모든 칸을 방문하며 각 칸에서 BFS를 진행하는데, 이미 이전에 BFS를 통해 방문되었다면 continue 해준다. 이를 통해 방문되지 않은 모든 칸에서 다시 BFS를 수행하고 모든 국가를 방문할 수 있고, 이를 통해 연합 정보를 종합할 수 있다. 연합 정보는 BFS에 의해 union_map에 기록된다.

 

이때 BFS를 진행하면서 범위를 벗어나는 경우와 이미 방문한 경우는 다시 진입하지 않도록 신경 써주어야 한다!

방문하지 않은 경우는, 해당 인덱스를 처음 방문하는 것이므로 인덱스를 queue에 넣어준 뒤, 방문 체크를 해야 한다.

 

그리고 union과 visited 배열은 사용하기 전에 계속 초기화해야 한다.

만약 계속 답이 1 이상의 값이 나오지 않는다거나 1번의 이동 후 변화가 없다면 visited 배열의 초기화 여부를 의심해볼 수 있다.

visited 배열을 초기화해주지 않았다면 1번의 탐색 후 이미 visited 배열이 모두 true로 되어있어 더 이상의 BFS 탐색이 진행되지 않아 결과가 달라지지 않았을 것이다.

 

 

(3) (4)

2번 과정을 통해 얻은 union_map과 기존의 인구 정보를 갖고 있는 map을 이용하여 각 연합 별 인구 이동을 진행한다.

                                  초기 인구 형태                                           1차 이동 조건의 연합 정보                                1차 이동 후의 인구 형태                                                                             

1차 이동이 진행되는 과정을 보여주는 사진이다. 위처럼 연합끼리 인구의 평균으로 조정되는 것을 확인할 수 있다.

 

move_people 함수에서 union_map과 map을 이용하여

각 연합별 도시의 개수를 count_region 배열에 저장하고, 각 연합별 인구의 총합을 sum_region 배열에 저장했다.

이후 sum_region 배열을 count_region 배열로 나누어 연합 별 인구의 평균을 구했다.

이때 나누는 과정에서 count_region 이 0인 경우 예외 처리를 해주어야 한다.

 

 

(5) (6)

solve 함수 내부에서 (2)~(4) 과정을 반복하며 횟수를 기록하는데 이때 이 반복문을 벗어나기 위한 조건으로 인구 이동 유무를 이용했다.

move_people 내부에서 map의 변화를 확인하여 map 이 변화되었다면 1을 return 하고, 변화가 없었다면 0을 return 하도록 구현했다.

solve 함수의 반복문 내에서 move_people의 반환 값으로 0 이 반환되어 인구 이동이 없었다면, 반복문을 벗어나게 구현하였다.

이후 sovle에 의해 증가되었던 ans 값을 출력하도록 구현하였다.

 

 

소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

#define max_rc 50
#define ABS(x)  (((x)<0)? -(x):(x))
using namespace std;

int map[max_rc][max_rc];
bool visited[max_rc][max_rc]={false,};
int union_map[max_rc][max_rc];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

int N, min_gap, max_gap;

void Input(){
    cin >> N >> min_gap >> max_gap;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> map[i][j];
        }
    }

}


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

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

queue<pair<int, int>> q;

/*
 * 해당 함수는 bfs 알고리즘을 통해 연결할 수 있는 나라들을 하나의 연합으로
 * union_map 배열에 표시해주는 함수이다.
 * 
 * 해당 입력에 대해 union_map 에 아래와 같은 결과가 저장된다.
 * [입력]
 * 4 10 50
 * 10 100 20 90
 * 80 100 60 70
 * 70 20 30 40
 * 50 20 100 10
 *
 * [결과]
 * 1 2 3 3
 * 3 3 3 3
 * 3 3 3 3
 * 3 3 4 3
 * 
 * 해당 결과로 생성된 union_map 은
 * move people 함수에서 동일한 숫자별 갯수와 인구 총합을 구하는 것에 이용된다.
 * 
 */

void make_union(){
    //초기화
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            union_map[i][j] = 0;
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            visited[i][j] = false;
        }
    }
    int u_number = 1;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(visited[i][j]) continue;

            q.push({i,j});
            union_map[i][j]=u_number;
            while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();

                for(int i=0; i<4; i++){
                    int newX = x + dir[i][0];
                    int newY = y + dir[i][1];
                    //배열 벗어나는 경우 continue 처리
                    if(newX<0 || newX>=N || newY<0 || newY>=N) continue;
                    
                    //현재까지 도달하면 배열 안에 존재하는 새로운 위치를 나타낸다.
                    //두 칸의 차이가 조건을 만족한다면 연합에 포함시킨다.
                    int gap = ABS(map[x][y]-map[newX][newY]);
                    if(min_gap<= gap && gap <= max_gap){
                        //조건 통과 -> 열린 길이 있다 -> 인구 이동이 발생한다
                        if(!visited[newX][newY]){
                            visited[newX][newY] = true;
                            union_map[newX][newY] = u_number;
                            q.push({newX,newY});
                        }
                    }
                }
            }
            u_number++;
        }
    }
}


/*
 * make_union 함수를 통해 얻은 union_map 을 통해
 * 각 지역별 인구의 평균을 구하고 map 에 업데이트 해주는 함수이다.
 * 
 * solve 과정에서 더 이상의 인구 변화가 없음을 탐지하기 위해,
 * beforemap 에 초기 map 을 저장한 뒤 map 업데이트를 진행한다.
 * 
 * 이후 함수 끝 부분에서 beforemap 과 map 의 비교
 * 변화가 있었다면 1을 return 하고,
 * 변화가 없었다면 0을 return 하여,
 * solve 부분에서의 반복문 종료에 사용한다.
 * 
 */


int move_people(){
    //인구 이동 전후 결과 비교를 위해 beforemap으로 저장
    int beforemap[max_rc][max_rc];
    for(int i=0;i<N;i++){
        for(int j=0; j<N; j++){
            beforemap[i][j]=map[i][j];
        }
    }

    //도시 갯수와 인구 총합을 위한 배열 선언 및 초기화
    int count_region[2501];
    int sum_region[2501];
    memset(count_region,0,sizeof(int)*2501);
    memset(sum_region,0,sizeof(int)*2501);

    //도시 갯수와 인구 총합 구하기
    for(int i=0;i<N;i++){
        for(int j=0; j<N; j++){
            count_region[union_map[i][j]]++;
            sum_region[union_map[i][j]]+=map[i][j];
        }
    }

    //인구 평균 구하기
    for(int i=0;i<2501;i++){
        if(count_region[i]==0) continue;
        sum_region[i]=sum_region[i]/count_region[i];
    }

    //인구 평균 적용하기
    for(int i=0;i<N;i++){
        for(int j=0; j<N; j++){
            map[i][j] = sum_region[union_map[i][j]];
        }
    }

    //인구 변화가 있는지 확인하고 변화가 있다면 1을 return
    //변화가 없다면 solve 의 while 문 중단을 위해 0 을 return
    for(int i=0;i<N;i++){
        for(int j=0; j<N; j++){
            if(map[i][j]!=beforemap[i][j]) return 1;
        }
    }

    return 0;
}

int ans=0;

void solve(){
    while(ans<2000){
        //각 연합을 만드는 함수
        make_union();
        //각 연합별로 인구 이동을 진행하고, 변화를 확인한다.
        if(move_people()==0) break;
        ans++;
    }
}

int main(){
    Input();
    solve();
    cout << ans;
}

 

 

결과 및 후기

이 문제를 풀 때 1시간 50분이 소요되었다. 아직 많이 부족한 수준이지만 내가 접근한 방식대로의 논리로 문제를 풀어냈다는 것이 뿌듯했다.