[C++] 16234 - 인구 이동 (골드5)

1. 문제 설명

 

16234번: 인구 이동

---

2. 아이디어

 

처음 보자마자 무식한 방법으로 로직은 떠오르는데 탐색이 너무 많이 필요해서 통과가 될까 싶었지만 입력 조건에 인구 이동 발생 일수가 최대 2,000번밖에 되지 않는다고 했으므로 개의치 않아도 된다고 판단했다.

N은 MAX 50이므로 최대 2,500크기 인접 행렬 그래프를 그릴 수 있는데, 2,000번 반복한다고 해도 5,000,000번 이므로 시간 복잡도에 걸리지 않는다.

즉, 그래프를 순회하면서 인구 차이가 L이상 R 이하인 구역을 벡터에 넣고 총합을 구한 다음에 벡터의 사이즈 만큼 나눈 평균치를 맵에 갱신해주고 이를 반복해주면 쉽게 풀린다.

---

3. 코드

 

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

#define endl "\n"

using namespace std;
typedef tuple<int, int> tii;

int N, L, R;
bool flag;
int map[51][51];
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};


int bfs(tii start, bool visited[51][51], vector<tii> &v) {
    int sum = map[get<0>(start)][get<1>(start)];
    visited[get<0>(start)][get<1>(start)] = true;
    v.push_back({get<0>(start), get<1>(start)});

    queue<tii> q; q.push(start);

    while (!q.empty()) {
        tii now = q.front(); q.pop();
        int y = get<0>(now), x = get<1>(now);

        for (int i=0; i<4; i++) {
            int ny = y + d[i][0];
            int nx = x + d[i][1];

            if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[ny][nx]) {
                if (L <= abs(map[y][x] - map[ny][nx]) && abs(map[y][x] - map[ny][nx]) <= R) {
                    visited[ny][nx] = true;
                    flag = true;

                    q.push({ny, nx});
                    v.push_back({ny, nx});
                    sum += map[ny][nx];
                }
            }
        }
    } 

    return sum;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> L >> R;
    
    for (int i=0; i<N; i++) for (int j=0; j<N; j++) cin >> map[i][j];
    int day = 0;
    while (true) {
        bool visited[51][51] = {false,};
        flag = false;

        for (int r=0; r<N; r++) for (int c=0; c<N; c++) {
            if (!visited[r][c]) {
                vector<tii> v;
                int sum = bfs({r,c}, visited, v);
                int avg = sum / v.size();

                for (auto tmp : v) {
                    int y = get<0>(tmp), x = get<1>(tmp);
                    map[y][x] = avg;
                }
                v.clear();
            }
        } 

        if (flag) day++; 
        else break; 
    }
    cout << day << endl;
    
    return 0;
}