16234번 - 인구 이동

문제 풀이 시간 : 2시간

문제 요약

NxN크기의 땅 한칸마다 나라가 존재한다.
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라는 연합이 된다.
위의 조건에 해당하는 모든 나라가 연합이 되었다면 그 연합은 인구이동을 한다.
인구 이동은 (연합의 총 인구 수)/(연합을 이루는 나라의 개수) 가 된다.
인구이동이 더이상 이뤄지지 않을 때까지 반복하여 며칠 동안 인구 이동이 발생하는지 구해라

문제 풀이

이 문제는 bfs로 인접한 나라들의 인구를 비교하면서 풀면 간단하게 풀 수 있을 거라고 생각했다.

초기 코드

c++

#include <iostream>
#include <cmath>
#include <queue>
#include <set>

using namespace std;

int n, l, r, ans = 0;
int city[51][51], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool visited[51][51];
queue<pair<int, int>> q, q2, ali;
set<pair<int, int>> s;

bool check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    return true;
}

void find(int x, int y) {
    q.push({x, y}); //bfs탐색을 위한 큐
    ali.push({x, y}); //연합 확인을 위한 큐
    int people = city[x][y]; //연합의 인구 수
    visited[x][y] = true;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (check(tx, ty)) { //칸을 넘기지 않고
                if (!visited[tx][ty]) { //방문되지 않았다면
                    int sum = abs(city[x][y] - city[tx][ty]); //인접한 국가의 인구 수 차이
                    if (sum >= l && sum <= r) { //조건에 만족한다면
                        ali.push({tx, ty}); //연합에 추가
                        q.push({tx, ty}); //bfs큐에 추가
                        visited[tx][ty] = true; //방문처리
                        people += city[tx][ty]; //연합 인구수 증가
                    } else {
                        s.insert({tx, ty}); //만족하지 않으면 방문되지 않은 나라를 저장하는 set에 저장
                    }
                }
            }
        }
    }

    people = people / ali.size(); //연합의 각 나라의 인구 수 계산

    while (!ali.empty()) { //각 나라의 인구수 저장
        city[ali.front().first][ali.front().second] = people;
        ali.pop();
    }
    if (!s.empty()) { //연합에 포함되지 않았던 나라들 다시 bfs
        ans++;
        while (true) {
            if (s.empty())
                break;
            x = (*s.begin()).first;
            y = (*s.begin()).second;
            s.erase(s.begin());
            if (!visited[x][y])
                break;
        }
        find(x, y);
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> city[i][j];
        }
    }

    int sum = 0;
    while (true) {
        sum++;
        find(1, 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                visited[i][j] = false;
        }
        if (ans == n * n - 1)
            break;
        ans = 0;
    }
    cout << sum - 1;
}

위 코드도 바로 통과를 했다.

근데 아무리 생각해도 저렇게 비효율적으로 할 필요가 있을까?

라는 생각을 하고 다른 사람들은 어떻게 풀었나 한번 찾아봤더니

굳이 s라는 set를 사용하지 않고 방문되지 않은 나라를 탐색하는 방식으로 해도 된다.

나라 개수가 아무리 많아봤자 50x50=2500이므로 시간초과와는 거리가 멀다.

그래서 다시 코드를 수정해서 아래와 같은 결과를 얻을 수 있었다.

최종 코드

c++

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

using namespace std;
vector<pair<int, int>> v;
queue<pair<int, int>> q;
int n, l, r, sum = 0;
int city[51][51], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool visited[51][51];

bool check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n)
        return false;
    return true;
}

void find(pair<int, int> input) {
    q.push(input); //bfs탐색을 위한 큐
    visited[input.first][input.second] = true; //방문 처리
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (!visited[tx][ty]) {
                if (check(tx, ty)) {
                    int temp = abs(city[x][y] - city[tx][ty]);
                    if (temp >= l && temp <= r) {
                        v.push_back({tx, ty}); //연합 처리를 위한 벡터 저장
                        q.push({tx, ty});
                        visited[tx][ty] = true;
                        sum += city[tx][ty]; //인구수 계산
                    }
                }

            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cin >> city[i][j];
    }
    bool flag = true;
    int ans = 0;
    while (flag) { //연합이 발생하지 않을 때까지 반복
        flag = false;
        for (int i = 1; i <= n; i++) { //모든 나라를 보며 방문되지 않은 경우 bfs실시
            for (int j = 1; j <= n; j++) {
                if (!visited[i][j]) {
                    v.push_back({i, j});
                    sum = city[i][j];
                    find({i, j});
                }
                if (v.size() > 1) { //벡터에 2개이상의 나라가 저장됐다면 연합 발생
                    flag = true;
                    for (int k = 0; k < v.size(); k++) {
                        city[v[k].first][v[k].second] = sum / v.size();
                    }
                }
                v.clear();
            }
        }
        if (flag)
            ans++;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                visited[i][j] = false;
        }

    }
    cout << ans;
}