[BFS] 16234번 인구 이동

16234번 인구 이동

 

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

 

문제

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]의 값이다. (1 ≤ A[r][c] ≤ 100)

 

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

 

예제 입력

2 20 50
50 30
20 40

2 40 50
50 30
20 40

2 20 50
50 30
30 40

3 5 10
10 15 20
20 30 25
40 22 10

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

 

예제 출력

1

0

1

2

3

 

 

해결방법

삼성 SW 역테 기출 문제이다

문제는 BFS : Flood Fill 을 활용하여 해결해야했다

 

⭐️첫번째 솔루션⭐️

• 1) Flood Fill로 탐색을 하며 인구 이동 지역은 chk 배열 값을 true 로 설정한다
• 2) 이동하면서 sum과 count 값을 설정해준다
• 3) BFS 탐색이 끝났으면 chk 배열이 true 인 곳을 avg 값으로 설정해준다

 

위의 3가지 구현은 어렵지 않게 구현했다

하지만 BFS 수행을 얼마나 해야하는지, 어떤 조건일 때 수행하는지가 솔루션으로 남았다

 

 

⭐️두번째 솔루션⭐️

BFS 수행은 무한 루프를 돌아야 했고, 연합을 맺을 수 있는 위치에서만 탐색을 수행해야했다

또한 인구 이동에 대해서 이해를 해야했다

블로그 참고

이 개념이 이해가 잘 되지 않아서 시간을 많이 투자했다

 

개념을 익히고 처음 구현한 코드에서 ⏱시간 초과 가 발생했다....

흑……ㅠㅠㅠ 내일 다시 해봐야겠다...

 

 

⭐️세번째 솔루션⭐️

시간초과를 해결했다!!! (사실 블로그 도움 받음 ㅎ_ㅎ)

앞에서 시간초과가 발생했기 때문에 원인을 찾아야 했다

• BFS 탐색의 무한루프 Break 시점
• Visit 배열을 관리하여 If 문 설정

 

먼저 visit 배열이 방문하지 않은 곳에서 BFS 탐색을 수행한다

X	X	X
X	X	X
	X

 

첫번째 0,0 에서 BFS 탐색을 한 후, visit 배열로 체크를 해준다

이제 2,0 과 2,2 가 남았는데 이 노드 또한 방문하지 않았기에 BFS 탐색을 수행한다

하지만 상 하 좌 우 모두 연합을 만들 수 없는 조건이다

따라서 vector에는 자기 자신의 위치만 들어가있으므로 인구 이동이 일어나지 않는다

 

 

이제 BFS 탐색에서 무한 루프를 종료시키는 조건을 설정해야한다

처음에는 bool 메소드를 만들어서 각 노드마다 방문해 상 하 좌 우 로 연합을 만들 수 있는지 체크했다

하지만 이는 너무 많은 시간을 잡아먹었다

위의 블로그에서 참고한대로 flag 변수(초기값 False) 를 두고 만약 연합이 만들어져 인구 이동이 일어 났다면 True 로 설정해줬다

 

만약 전체 노드의 체크가 끝났다면 flag 값을 조건문의 조건으로 설정하여

• True : ans++
• False : break

를 해주었다

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;

typedef pair<int, int> pii;

int n,l,r;
int sum,cnt,ans;
bool flag;

int map[MAX][MAX];
bool visit[MAX][MAX];

vector<pii> v;

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

void movePopulation(){
    int avg = sum / cnt;
    
    for(int i=0; i<v.size(); i++){
        int x = v[i].first;
        int y = v[i].second;
        map[x][y] = avg;
    }
}

void bfs(int i,int j){
    queue<pii> q;
    q.push(pii(i,j));
    v.push_back(pii(i,j));
    visit[i][j] = true;
    sum += map[i][j];
    cnt++;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int k=0; k<4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
            if(visit[nx][ny]) continue;
            
            int sub = abs(map[x][y] - map[nx][ny]);
            if(sub>=l && sub<=r){
                visit[nx][ny] = true;
                sum += map[nx][ny];
                cnt++;
                q.push(pii(nx,ny));
                v.push_back(pii(nx,ny));
            }
        }
    }
    // 인구 이동
    if(v.size() > 1) {
        movePopulation();
        flag = true;
    }
    // 초기화
    v.clear();
    sum = 0;
    cnt = 0;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> l >> r;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
    
    ans = 0; sum = 0; cnt = 0;
    
    while(true){
        memset(visit, false, sizeof(visit));
        flag = false;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visit[i][j]){
                    bfs(i,j);
                }
            }
        }
        
        if(flag) ans++;
        else break;
    }
    
    cout << ans << "\n";
}