[백준] 16234번: 인구 이동 - C++

문제 출처:https://www.acmicpc.net/problem/16234

---

문제

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

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

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

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

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

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

문제 자체는 DFS나 BFS를 이용하여 조건에 맞추어 인구 이동이 가능한 영역을 구하고 이 영역 안에서 인구 이동을 시킵니다.

이 인구 이동을 더 이상 불가능 할때까지 계속 반복하며 인구이동 발생 수를 체크만 해주면 되는 비교적 간단한 문제인데 

저는 문제에서 말하는 '인구 이동'을 잘 못 이해하여 문제를 푸는데 한참 걸렸습니다.

제가 헷갈린 인구 이동은 아래와 같습니다.

L = 10, R = 50

이런 형태로 입력이 주어졌다고 합시다.

주어진 배열에 대하여 인구 이동이 가능한 영역을 위와같이 구해줍니다.

조건에 맞게 배열을 변형시켜준 뒤 인구 이동 횟수를 1 증가시킵니다. 

변형된 배열에 맞추어 한번 더 인구 이동이 가능한 영역을 구합니다.

여기서 한 구역을 조건에 맞추어 바꿔주었는데 이 때 인구 이동 횟수를 1 증가시키면 안됩니다. 

이렇게 모든 영역을 전부 다 바꿔준 뒤에야 인구 이동 횟수를 1 증가시켜주어야 합니다.

저는 처음에 구역 한개가 바뀔때마다 인구 이동 횟수를 증가시키는 줄 알고 한참을 고생했습니다.

이 부분만 주의해서 풀면 그렇게 어렵지 않게 풀이가 가능할거라 생각됩니다.

그리고 더 이상 인구 이동이 가능하지 않아서 프로그램을 종료하는 조건은 저의 경우 아래와 같은

형식으로 풀었습니다.

위의 배열에 대하여 영역을 구했을때 똑같은 크기의 배열을 하나 더 만들어 아래처럼 숫자로 각 구역을 

표시 해 주었습니다. 따라서 어떤 배열이 주어졌을때 아래처럼 영역을 숫자로 나타낸 배열이 

이와 같은 형식을 나타낸다면 모든 구역이 전부 독립적인 영역을 가진다는 의미이므로 이 때 프로그램을 

종료시켜 주었습니다.

전체 코드입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
#include <limits>
 
using namespace std;
int n, l, r, **arr, **area, dp[2501], sum = 0, cnt = 0;
 
//영역을 구해주는 DFS함수 입니다.
void DFS(int x, int y, int num) {
    area[y][x] = num;
    sum += arr[y][x];
    cnt++;
    if (y > 0 && l <= abs(arr[y][x] - arr[y - 1][x]) && abs(arr[y][x] - arr[y - 1][x]) <= r && area[y - 1][x] == 0)
        DFS(x, y - 1, num);
    if (y < n - 1 && l <= abs(arr[y][x] - arr[y + 1][x]) && abs(arr[y][x] - arr[y + 1][x]) <= r && area[y + 1][x] == 0)
        DFS(x, y + 1, num);
    if (x > 0 && l <= abs(arr[y][x] - arr[y][x - 1]) && abs(arr[y][x] - arr[y][x - 1]) <= r && area[y][x - 1] == 0)
        DFS(x - 1, y, num);
    if (x < n - 1 && l <= abs(arr[y][x] - arr[y][x + 1]) && abs(arr[y][x] - arr[y][x + 1]) <= r && area[y][x + 1] == 0)
        DFS(x + 1, y, num);
}
 
 
void init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            area[i][j] = 0;
        }
    }
}
 
//프로그램이 끝나는 조건을 나타내는 함수 
int end() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (area[i][j] != (i*n) + j + 1)
                return 1;
        }
    }
    return 0;
}
 
int main(void)
{
    int num = 1, result = -1;
    scanf("%d %d %d", &n, &l, &r);
    arr = new int*[n];
    area = new int*[n];
    
    for (int i = 0; i < n; i++) {
        arr[i] = new int[n];
        area[i] = new int[n];
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            area[i][j] = 0;
        }
    }
 
    do {
        init();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (area[i][j] == 0) {
                    DFS(j, i, num);
                    dp[num] = sum / cnt;
                    cnt = 0; sum = 0;
                    num++;
                }
            }
        }
        num = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = dp[area[i][j]];
            }
        }
        result++;
    } while (end());
 
    printf("%d", result);
    return 0;
}