[C++] 16234. 인구이동

 

이번 문제는 bfs문제이다.

백준의 토마토와 비슷한 문제이다.

토마토도 괜찮은 문제이니 한번 풀어보길 추천한다! -> 토마토 문제 바로가기

 

 

전체 영토 중 방문하지 않은 영토부터 차례대로 순회를 시작한다.

큐에 넣어놓고 주변 영토(상하좌우)를 방문해보며 연합이 될 수 있는지 조건을 체크한다.

연합이 될 수 있으면 bfs용 큐와 연합들을 저장할 벡터에 저장해주고 총합을 더해준다. (나중에 인구수 조정을 위함)

연합이 만들어졌다면 (2개이상) 인구수를 조정해준다.

 

두번째 for루프에서 방문을 검사하는 코드, 즉 bfs를 실행하는 코드는 같은 날 다른 연합을 또 만들어야하므로 연합을 저장해주는 벡터를 초기화해준다.

두개의 for루프가 끝나고 연합이 아직 남아있다면 days를 증가시켜주고 위 과정을 연합이 만들어지지않을때까지 반복한다.

 

 

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

/*
<문제 정리>
NxN r행 c열 인구 = A[r][c], 인접 나라(상하좌우 4개) 국경선 존재
- (국경선 공유 두 나라 인구차이) >=L, =<R이면 국경선 오픈
- 하루동안 인구이동 진행, 인접 칸만 이용해 이동가능, 이런 나라들 = 연합
- 연합 각 칸의 인구수 = 연합 인구수 / 연합 이루는 칸 개수 (소수점 버림)
- 연합 해체 후 국경선을 닫음
인구 이동이 며칠동안 발생하는지?
-> 2차원 bfs (토마토 문제)
*/

#define MAX 51
queue<pair<int, int>> q;
vector<pair<int, int>> v;
int N, L, R, A[MAX][MAX];
bool visited[MAX][MAX];
bool guild = true;

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int sum = 0;

void bfs(pair<int,int> start)
{
    q.push(start);
    visited[start.first][start.second] = true;

    while(!q.empty()) {

        int x = q.front().first;
        int y = q.front().second;

        q.pop();

        for(int i=0; i<4; i++) {

            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]) {
                int near = abs(A[x][y] - A[nx][ny]);
                if(near >= L && near <= R) {
                    q.push(make_pair(nx,ny));
                    visited[nx][ny] = true;
                    v.push_back(make_pair(nx,ny));
                    sum += A[nx][ny];
                }
            }
        }
    }
}

void clearVisit() {
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) visited[i][j] = false;
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> L >> R;

    // inputs
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> A[i][j];
        }
    }
    
    int days = 0;

    while(guild) {
        guild = false;
        // 전체 영토 순회
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    v.clear();
                    v.push_back(make_pair(i,j));
                    sum = A[i][j];
                    bfs(make_pair(i,j));
                }

                // bfs 통해 길드 만들어 옴
                if(v.size() >= 2) {
                    guild = true;
                    for(int k = 0; k < v.size(); k++) {
                        A[v[k].first][v[k].second] = sum / v.size();
                    }
                }
            }
        }
        if(guild) days++;
        clearVisit();
    }

    cout << days;

    return 0;
}