Algorithm 문제

[백준] 16234 - 인구 이동

노예2 2019. 7. 23. 14:40

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

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명

www.acmicpc.net

간단한 탐색 문제이고 queue를 이용한 dfs로 풀었다.

 

<C++ 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;
 
int country[50][50];
int vis[50][50];
int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
 
int main(){
    int n, l, r;
    scanf("%d %d %d", &n, &l, &r);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &country[i][j]);
        }
    }
    int re = 0;
    while(true){
        bool move = false;
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!vis[i][j]){
                    vis[i][j] = true;
                    queue<pair<int, int> > q;
                    vector<pair<int, int> > v;
                    int sum = country[i][j];
                    q.push(make_pair(i, j));
                    v.push_back(make_pair(i, j));
                    while(!q.empty()){
                        int y = q.front().first, x = q.front().second;
                        q.pop();
                        for(int d=0; d<4; d++){
                            int ay = y + dy[d], ax = x + dx[d];
                            if(ay >= 0 && ay < n && ax >= 0 && ax < n && !vis[ay][ax] && abs(country[ay][ax] - country[y][x]) >= l && abs(country[ay][ax] - country[y][x]) <= r){
                                vis[ay][ax] = true;
                                q.push(make_pair(ay, ax));
                                v.push_back(make_pair(ay, ax));
                                sum += country[ay][ax];
                            }
                        }
                    }
                    if(v.size() > 1){
                        int avg = sum / v.size();
                        for(int k=0; k<v.size(); k++){
                            country[v[k].first][v[k].second] = avg;
                        }
                        move = true;
                    }
                }
            }
        }
        if(!move) break;
        else re++;
    }
    printf("%d", re);
    return 0;
}
cs