[백준] 16234번: 인구 이동

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

16234번: 인구 이동

삼성 코딩테스트 연습하기에 좋았던 시뮬레이션 & 탐색 문제이다.

평소에 DFS를 할 때 자주 inside 함수를 생성하는 것을 잊는다. 실수하지 말아야 한다.

그리고 해당 문제는 반복되는 일련의 과정 속에서 연합을 따로 구해서 처리를 해야 하는데, 그 때 연합끼리의 정보가 서로 침법하지 ㅇ낳도록 주의해야 한다.

여기선 한 연합에서 이미 인구 수를 조정한 것이 다음 연합에 영향을 주어서 처음에 실패하였다.

하지만 방문 여부를 판단하여 해당 칸은 포함하지 않도록 처리하였다.

 

그리고 연합에 속하는 나라를 일일이 방문하여 판단하지 않고 Queue를 사용해 위치를 바로 파악할 수 있도록 하였다.

참고로 큰 사이즈의 배열을 만드는 것은 공간을 차지할 뿐만 아니라, 초기화나 생성에도 큰 시간이 소요된다.

따라서 활용하는 배열을 최소화해야 한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int countries[50][50];
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

bool inside(int r, int c, int n) {
    return r >= 0 && r < n && c >= 0 && c < n;
}
void dfs(int i, int j, int l, int r, int n, int &cnt, int &pop_sum, vector<vector<bool>> &visited, queue<pair<int,int>> &q) {
    for(int d = 0;d < 4;d++) {
        int nr = i + dr[d];
        int nc = j + dc[d];
        int diff = countries[i][j] - countries[nr][nc];
        if(diff < 0) diff *= -1;
        
        if(inside(nr, nc, n) && diff >= l && diff <= r && !visited[nr][nc]) {
            visited[nr][nc] = true;
            q.push({nr, nc});
            cnt++;
            pop_sum += countries[nr][nc];
            dfs(nr, nc, l, r, n, cnt, pop_sum, visited, q);
        }
    }
}

int main(void) {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, l, r, num = 0;
    cin >> n >> l >> r;
    
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> countries[i][j];
        }
    }
    
    while(true) {
        bool changed = false;
        
        vector<vector<bool>> visited(n, vector<bool>(n, false));
    
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                if(!visited[i][j]) {
                    queue<pair<int, int>> q;
                    int cnt = 1, pop_sum = countries[i][j];
                    visited[i][j] = true;
                    q.push({i, j});
                    dfs(i, j, l, r, n, cnt, pop_sum, visited, q);
                    
                    if (cnt == 1) {
                        continue;
                    }
                    
                    int result = pop_sum / cnt;

                    while(!q.empty()) {
                        auto pos = q.front();
                        q.pop();
                        int a = pos.first;
                        int b = pos.second;
                        visited[a][b] = true;
                        if(result != countries[a][b]) {
                            countries[a][b] = result;
                            changed = true;
                        }
                    }

                }
            }
        }
        
        if(!changed) {
            break;
        }
        
        num++;
    }
    
    cout << num << '\n';
}