백준 16234 : 인구 이동 (dfs)

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

예제 입력 1 복사

2 20 50
50 30
20 40

예제 출력 1 복사

1

예제 입력 2 복사

2 40 50
50 30
20 40

예제 출력 2 복사

0

 

경계를 공유하는 나라의 인구 차이가 모두 L보다 작아서 인구 이동이 발생하지 않는다.

..

 

• 풀이

 

각  지점마다 기존에 방문한적 없으면 4방향 dfs로 연합을 만든다

연합에 들어간 국가의 수와, 인구 이동후 값을 저장하기 위해서 방문여부, 좌표, 인구수를 저장해두고

각 dfs가 끝난 후 인구를 재배치한다

인구 이동이 없을때까지 반복

 

visited를 각 dfs할때마다 초기화해버리면 이미 인구이동이 일어나면서 방문한 국가를 또 다시 방문하면서 꼬인다..

전체 n*n에 dfs를 수행하는 n*n번 초기화하면 안되고, dfs를 호출하기 전에 visited를 초기화한다

 

dfs하면서 방문한 국가는 저장해뒀다가 탈출하면 그때 인구이동을 한다

void solution(){
    while(true){
        bool isUnion = false;
        //visited를 각 dfs마다 초기화하면 안되고, 전체 영역에서 dfs를 쫙 돌릴때마다 초기화
        visited.clear();
        visited.resize(n,vector<bool>(n,false));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(!visited[i][j]){
                    // 연합국가 리스트는 dfs를 할때마다 초기화해줘야 해당 구역에서 연합된거 찾을 수 있음
                    country.clear();
                    sum = arr[i][j];
                    country.push_back({i,j});
                    visited[i][j] = true;
                    dfs(i,j,country);
                    //크기가 1이면 연결된 나라가 없음
                    if (country.size() == 1) continue;
                    for(auto x : country){
                        arr[x.first][x.second] = sum / country.size();
                        isUnion = true;
                    }
                }
            }
        }
        if(!isUnion) break;
        cnt++;
    }
}

 

dfs 에서는 국경을 열 수 있으면 나라 목록에 추가하고 인구수를 합쳐서 저장했다

void dfs(int dy, int dx, vector<pair<int, int>> &v){
    for(int i = 0; i < 4; i++){
        int ny = dy + pos[i][0];
        int nx = dx + pos[i][1];
        if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
        if(visited[ny][nx]) continue;
        int tmp = abs(arr[ny][nx] - arr[dy][dx]);
        //국경을 열수 있는 조건
        if(l <= tmp && tmp <= r){
            visited[ny][nx] =1;
            sum += arr[ny][nx];
            v.push_back({ny, nx});
            dfs(ny, nx, v);
        }
    }
}

 

- 전체 코드

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

using namespace std;



int pos[4][2] = {{1, 0},{0, 1},{-1, 0},{0,  -1}};
int n, l, r, sum, cnt = 0;
vector<vector<int>> arr;
vector<vector<bool>> visited;
vector<pair<int, int>> country;

void dfs(int dy, int dx, vector<pair<int, int>> &v){
    for(int i = 0; i < 4; i++){
        int ny = dy + pos[i][0];
        int nx = dx + pos[i][1];
        if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
        if(visited[ny][nx]) continue;
        int tmp = abs(arr[ny][nx] - arr[dy][dx]);
        //국경을 열수 있는 조건
        if(l <= tmp && tmp <= r){
            visited[ny][nx] =1;
            sum += arr[ny][nx];
            v.push_back({ny, nx});
            dfs(ny, nx, v);
        }

    }
}

void solution(){
    while(true){
        bool isUnion = false;
        //visited를 각 dfs마다 초기화하면 안되고, 전체 영역에서 dfs를 쫙 돌릴때마다 초기화
        visited.clear();
        visited.resize(n,vector<bool>(n,false));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(!visited[i][j]){
                    // 연합국가 리스트는 dfs를 할때마다 초기화해줘야 해당 구역에서 연합된거 찾을 수 있음
                    country.clear();
                    sum = arr[i][j];
                    country.push_back({i,j});
                    visited[i][j] = true;
                    dfs(i,j,country);
                    //크기가 1이면 연결된 나라가 없음
                    if (country.size() == 1) continue;
                    for(auto x : country){
                        arr[x.first][x.second] = sum / country.size();
                        isUnion = true;
                    }
                }
            }
        }
        if(!isUnion) break;
        cnt++;
    }
}

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

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

    solution();
    cout << cnt;
    return 0;
}