[BOJ] 16234 : 인구 이동

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

16234번: 인구 이동

문제 유형 : BFS / DFS

문제 난이도 : GOLD IV

 

문제

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]의 값이다. (0 ≤ A[r][c] ≤ 100)

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

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

풀이

1.인구 이동이 없을때까지 다음 반복문을 반복한다:

  2.방문 여부를 담는 이차원 배열을 생성한다.

  3.인구수가 담긴 이차원 배열을 방문한다:

     4.만약, 방문한적 없는 나라이면, 큐에 추가하고, 탐색을 시작한다.

     5. 인접한 연합 가능한 국가들과 연합을 최대한 맺는다 새로 연합된 국가들은 또 큐에 넣는다.

     6. 5를 큐가 빌 때까지 반복한다.

   7.큐가 빈 후연합이 끝나면, 인구 수를 배분한다.

   8. 인구 이동이 없다면, 반복문을 종료한다.

   9. 인구 이동이 있다면 시간을 누적시키고 다시 1로 간다.

 

코드(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

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

    vector<vector<int>> population(n, vector<int>(n));

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

    int days = 0;

    while (true)
    {
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        bool moved = false;

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (!visited[i][j])
                {
                    vector<pair<int, int>> unionCountries;
                    int totalPopulation = 0;

                    queue<pair<int, int>> q;
                    q.push({i, j});
                    visited[i][j] = true;
                    unionCountries.push_back({i, j});
                    totalPopulation += population[i][j];

                    while (!q.empty())
                    {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();

                        for (int k = 0; k < 4; ++k)
                        {
                            int nx = x + dx[k];
                            int ny = y + dy[k];

                            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny])
                            {
                                int diff = abs(population[x][y] - population[nx][ny]);
                                if (diff >= l && diff <= r)
                                {
                                    q.push({nx, ny});
                                    visited[nx][ny] = true;
                                    unionCountries.push_back({nx, ny});
                                    totalPopulation += population[nx][ny];
                                }
                            }
                        }
                    }

                    if (unionCountries.size() > 1)
                    {
                        moved = true;

                        int avgPopulation = totalPopulation / unionCountries.size();
                        for (const auto &country : unionCountries)
                        {
                            population[country.first][country.second] = avgPopulation;
                        }
                    }
                }
            }
        }

        if (!moved)
        {
            break;
        }

        days++;
    }

    cout << days << '\n';

    return 0;
}