[16234번] 인구 이동(삼성 코딩테스트 SW)

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

 

문제접근법.

1. 국경선이 열린다는 것은 인접한 배열사이의 차이가 L 이상 R 이하가 된다는 것을 의미한다.

2. 연합이 파악되면, 해당되는 칸들은 값을 바로 변경해줘도 무관하다. 체크 배열을 통해서, 해당 칸들이 이용되지 않도록 할 것이다.

3. 연합에 해당되는 값들을 DFS로 탐색하되 값들을 저장해두고 싶다. 자료구조를 사용한다.

 

 

문제에 대한 오해.

- 1번의 인구 이동은 1개 연합의 발생을 의미하는 것이 아니라, 현재의 배열에서 발생할 수 있는 모든 연합을 1번의 인구이동으로 보는 것이다. 문제의 조건을 읽다보면, 인구 이동이 몇 일을 걸쳐서 발생하는지 묻고 있는지를 파악할 수 있을 것이다.

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
 
int N, L, R;
int arr[51][51];
int check[51][51];
int answer = 0;
int op[5][2] = { {},{1,0},{-1,0},{0,1},{0,-1} };
int sum = 0, move_check = 0;
vector<pair<int, int>> v;
 
void dfs(int i, int j) {
    if (check[i][j] != 0)
        return;
 
    check[i][j] = 1;
    sum += arr[i][j];
 
    for (int k = 1; k <= 4; k++) {
        int n_i = i + op[k][0];
        int n_j = j + op[k][1];
 
        if (n_i < 1 || n_j < 1 || n_i > N || n_j > N || check[n_i][n_j] == 1)
            continue;
        
        int diff = abs(arr[i][j] - arr[n_i][n_j]);
        if (L <= diff && diff <= R) {
            v.push_back(make_pair(n_i, n_j));
            dfs(n_i, n_j);
        }
    }
 
    return;
}
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> N >> L >> R;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    while (1) {
        memset(check, 0, sizeof(check));
        move_check = 0;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                v.clear();
                sum = 0;
 
                if (check[i][j] == 0)
                {
                    v.push_back(make_pair(i, j));
                    dfs(i, j);
                }
 
                if (v.size() > 1) {
                    move_check = 1;
                    int add = sum / v.size();
                    for (int k = 0; k < v.size(); k++)
                        arr[v.at(k).first][v.at(k).second] = add;
                }
            }
        }
 
        if (move_check == 0)
            break;
 
        answer += 1;
    }
 
    cout << answer << endl;
    return 0;
}