[삼성SW테스트] 백준 16234번 - 인구 이동

삼성 SW역량 테스트 기출 문제이다. (유형: DFS 탐색)

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

16234번: 인구 이동

1x1칸으로 나뉘어진 땅에 각 나라가 존재하며, 조건에 맞게 나라간 국경선이 열리거나 닫혀 인구 이동이 일어난다고 한다. 각 나라가 인접한 나라와 특정 값 범위내로 인구 차이가 있다면 국경선이 열리고, 최종적으로 연합을 한 국가들의 수로 이 국가들의 모든 인구를 나누어 동일한 인구를 가진 뒤에 국경선이 닫히는 과정을 반복한다. 문제는 인구이동이 몇 번 이루어 지는지를 묻고 있다.

 

이 문제는 DFS 탐색으로 쉽게 풀 수 있다. 모든 방문여부 배열을 false로 초기화 하고 <1, 1> 위치부터 탐색하지 않으면 깊이우선탐색을 해서 연합으로 끼워넣을 수 있는 나라들을 벡터에 모두 넣는다. 만약 두 개 이상의 나라가 연합했다면 아직 인구이동이 이루어지는 과정이기 때문에 이들의 평균 인구를 각 나라에 모두 넣고 계속해서 while을 돌린다. 만약 모든 나라를 탐색해서 두 개 이상의 나라가 연합하는 경우가 발생하지 않는다면 인구이동이 이루어지지 않게되므로 인구이동이 발생한 횟수를 출력하고 종료하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 51
using namespace std;
int N, L, R;
int A[MAX][MAX];
bool check[MAX][MAX];
int answer = 0;
bool quit = true;
int people, country_cnt;
vector<pair<int, int> > v;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void falsing(){
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            check[i][j] = false;
}
 
void DFS(int r, int c){
    for (int i = 0; i < 4; i++){
        int n_r = r + direction[i].dr;
        int n_c = c + direction[i].dc;
        if (n_r >= 1 && n_r <= N && n_c >= 1 && n_c <= N){
            // 1. 범위 내에 있고,
            if (!check[n_r][n_c]){
                // 2. 방문하지 않았으며,
                if (abs(A[r][c] - A[n_r][n_c]) >= L && abs(A[r][c] - A[n_r][n_c]) <= R){
                    // 3. 두 나라의 차이가 조건에 맞다면
                    v.push_back(make_pair(n_r, n_c));
                    check[n_r][n_c] = true;
                    people += A[n_r][n_c];
                    country_cnt++;
                    DFS(n_r, n_c);
                }
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
 
    cin >> N >> L >> R;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++)
            cin >> A[i][j];
    }
 
    falsing();
    while (1){
        for (int r = 1; r <= N; r++){
            for (int c = 1; c <= N; c++){
                if (!check[r][c]){
                    check[r][c] = true;
                    v.push_back(make_pair(r, c));
                    people = A[r][c];
                    country_cnt = 1;
                    DFS(r, c);
                    if (country_cnt > 1){
                        for (int i = 0; i < v.size(); i++){
                            A[v[i].first][v[i].second] = people / country_cnt;
                        }
                        quit = false;
                    }
                    v.clear();
                }
            }
        }
 
        if (quit){
            cout << answer << '\n';
            break;
        }
        quit = true;
        falsing();
        answer++;
    }
    return 0;
}