[C++/백준] 16234번: 인구 이동

문제 링크

16234번: 인구 이동

 

풀이

DFS로 풀긴 했는데, BFS가 편했을 것 같다..

1. 값을 입력 받으며 벡터를 만든다.
2. 인구 이동이 있어 다시 확인해야 하는지 체크하기 위한 변수 flag가 true라면 계속 인구 이동 시킨다. 첫번째는 인구 이동을 해야하는지 체크해야 하므로 do-while문을 쓴다.
3. 벡터를 돌며 visited[i][j]가 0이면 탐색되지 않았다는 것이므로 dfs 함수로 탐색을 시작한다.
   1. dfs 함수에서는 상하좌우를 확인하며 gap이 범위 안에 있다면 재귀 호출을 한다.
   2. 영역 내의 총 합을 구하기 위한 sum과 영역 칸의 개수를 구하기 위한 cnt를 갱신한다.
   3. 영역 구분이 끝나면 arr의 값을 바꿔줘야 하므로 해당 위치 값을 갖는 unionArr에 추가한다.
4. dfs를 돌고 한 영역이라도 1보다 크다면(연합을 맺었다면) 인구 이동을 다시 체크해야 한다. flag를 true로 하고, arr의 값을 바꿔준다.
5. flag가 true일 때는 인구 이동을 위해 계속해서 days++ 해준다.
6. days를 출력하면 끝

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

int n, l, r;
int cnt = 0;
int sum = 0;
vector<pair<int, int>> unionArr;

void dfs(int y, int x, vector<vector<int>> &visited, vector<vector<int>> &arr)
{    
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
        if (visited[ny][nx]) continue;
        int gap = abs(arr[ny][nx] - arr[y][x]);
        if (gap >= l && gap <= r)
        {
            visited[ny][nx] = 1;
            dfs(ny, nx, visited, arr);
        }
    }
    sum += arr[y][x];
    cnt++;
    unionArr.push_back({ y,x });
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l >> r;

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

    vector<vector<int>> visited(n, vector<int>(n));
    bool flag = false; // 인구 이동이 있어 다시 체크해야 함
    int days = 0;
    do
    {
        visited.clear();
        visited.resize(n, vector<int>(n));

        flag = false;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (visited[i][j] == 0)
                {
                    sum = 0;
                    cnt = 0;
                    unionArr.clear();

                    visited[i][j] = 1;
                    dfs(i, j, visited, arr);
                    if (cnt > 1)
                    {
                        flag = true;
                    }
                    for (auto u : unionArr)
                    {
                        arr[u.first][u.second] = sum / cnt;
                    }
                }
            }
        }
        if (flag) days++;
    } while (flag);

    cout << days;
}