[BOJ 16234] 인구 이동 (C++)

인구 이동 (Gold 5)

문제

전체 문제 보기

16234번: 인구 이동

접근법

이번 문제는 DFS/BFS를 활용한 구현, 시뮬레이션 문제입니다. 여기서는 BFS를 활용해서 풀이를 진행합니다.

먼저 매일 한 번씩

• BFS탐색을 통해서 각 국가들의 인구수 차이를 확인하여 국경을 열어서 연합을 만들 수 있는지 확인
• 만들어진 연합의 평균 인구수 반환
• BFS로 반환받은 연합의 평균 인구수를 활용하여 각 연합별 인구 이동 결과 반영

위 작업을 더이상 인구가 이동하지 않을 때까지 반복하여 정답을 구할 수 있습니다.

최적화

위 방식으로 처음 이 문제에 접근할 때는 모든 국가에 대해서 BFS 탐색을 진행하는 방향으로 생각할 수 있습니다. 하지만, 어떤 날에 인구수가 변하지 않은 국가는 그다음 날에도 인구수가 변하지 않을 가능성이 매우 큽니다. 이 국가는 인접 국가가의 값이 변할 때까지 인구수가 변하게 될 일이 없습니다. 다음과 같은 예시를 생각해봅시다.

5 2 1000
10 10 10 10 999
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10

answer: 35일

위 예시에서 5행 1열의 값은 7일차까지 변하지 않을 것입니다. 그래서 매번 모든 국가에 대해서 BFS 탐색을 진행한다면 큰 낭비가 발생하게 됩니다. BFS탐색은 전날에 값의 변화가 있었던 국가들에 대해서만 진행할 경우 불필요한 연산을 대폭 줄일 수 있습니다. 그래서 인구수가 변화한 국가들의 위치를 큐에 저장하고, 매일 큐에 저장된 국가들에 대해서만 BFS 탐색을 진행하여 최적화할 수 있습니다. 그 결과 아래와 같이 실행시간을 약 400s에서 16ms로 성능 향상을 이뤄낼 수 있었습니다.

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

struct Node {
    int population{};
    int ID{-1};
};
struct Pos {
    Pos() {}
    Pos(int _r, int _c) : r{ _r }, c{ _c } {}
    int r{};
    int c{};
};
using Level = vector<vector<Node>>;
const int dr[4] = { 1, -1, 0, 0 };
const int dc[4] = { 0, 0, 1, -1 };
queue<Pos> updated;
int BFS(Level& level, int id, Pos start, int N, int L, int R)
{
    int sum{};
    int cnt{};
    level[start.r][start.c].ID = id;
    cnt++;
    sum += level[start.r][start.c].population;
    queue<Pos> q;
    q.push(start);
    //cout << "start: "<<start.r << ", " << start.c << endl;
    while (!q.empty())
    {
        Pos cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            Pos next(cur.r + dr[i], cur.c + dc[i]);
            if (next.r < 0 || next.r >= N || next.c < 0 || next.c >= N || level[next.r][next.c].ID != -1) continue;

            const int diff = abs(level[cur.r][cur.c].population - level[next.r][next.c].population);

            if (L <= diff && diff <= R)
            {
                //cout << "add: " << next.r << ", " << next.c << endl;
                cnt++;
                sum += level[next.r][next.c].population;
                level[next.r][next.c].ID = id;
                q.push({ next.r, next.c });
            }
        }
    }
    if (cnt == 1) {
        level[start.r][start.c].ID = -1;
        return -1;
    }

    int avg = sum / cnt;
    return avg;
}
void PrintAll(Level& level)
{
    cout << endl;
    for (auto& row : level)
    {
        for (Node& n : row)
            cout << n.population << " ";
        cout << endl;
    }
}
bool OneDay(Level& level, int N, int L, int R)
{
    // 국경 확인 및 이동인구 계산
    vector<int> avgs;
    while(!updated.empty())
    {
        Pos start = updated.front();
        updated.pop();        

        if (level[start.r][start.c].ID != -1) continue;
        int avg = BFS(level, avgs.size(), start, N, L, R);
        if(avg != -1) avgs.emplace_back(avg);
    }

    bool isMove = false;
    // 인구 이동 및 방문기록 초기화 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            const int ID = level[i][j].ID;
            // 값의 변화가 있는 경우 true
            if (ID != -1 && level[i][j].population != avgs[ID])
            {
                updated.push({ i,j });
                level[i][j].population = avgs[ID];
                isMove = true;
            }
        }
    }    

    //PrintAll(level);
    // 방문기록 초기화 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            level[i][j].ID = -1;
        }
    }

    return isMove;
}
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, L, R; // (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
    cin >> N >> L >> R;
    Level level(N, vector<Node>(N));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> level[i][j].population;
            updated.push({ i, j });
        }
    }
    int answer{};
    while (OneDay(level, N, L, R)) answer++;
    cout << answer;
    return 0;
}