[백준] 16234. 인구 이동

bfs를 사용해 주변 배열의 크기를 비교해서 uni벡터에 연합의 번호를 저장하고 이때 con벡터에 그 나라의 인구수와 위치를 저장하였다. 그리고 연합에 나라의 수가 1이 아니라면 문제에 나와있는대로 인구를 이동했다. while문으로 인구가 이동하지 않을때 까지 반복해서 답을 구하면 된다.

 

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
 
struct info {
    int x, y, cnt;
};
int N, L, R;
int dxy[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
vector<vector<int>> map;
vector<vector<int>> uni;
vector<vector<info>> con;
int num = 1;
void bfs(int a, int b) {
    uni[a][b] = num;
    con.push_back(vector<info>());
    con[num].push_back({ a,b,map[a][b] });
    queue<pair<int, int>> q;
    q.push({ a,b });
    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 + dxy[i][0];
            int ny = y + dxy[i][1];
 
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (uni[nx][ny] != 0) continue;
 
            if (L <= abs(map[x][y] - map[nx][ny]) && abs(map[x][y] - map[nx][ny]) <= R) {
                uni[nx][ny] = num;
                con[num].push_back({ nx,ny,map[nx][ny] });
                q.push({ nx,ny });
            }
        }
    }
 
}
void mix() {
 
}
int main()
{
    //freopen(input.txt, r, stdin);
    cin >> N >> L >> R;
    map.assign(N, vector<int>(N));
 
    int answer = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    int tmp = -1;
    while (tmp != answer) {
        num = 1;
        uni.assign(N, vector<int>(N, 0));
        con.assign(0, vector<info>());
        con.push_back(vector<info>());
 
        tmp = answer;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (uni[i][j] == 0) {
                    dfs(i, j);
                    num++;
                }
            }
        }
 
        bool flag = false;
        for (int i = 1; i < num; i++) {
            int cnt = 0;
            if (con[i].size() != 1) {
                for (int j = 0; j < con[i].size(); j++) {
                    cnt += map[con[i][j].x][con[i][j].y];
                }
                for (int j = 0; j < con[i].size(); j++) {
                    map[con[i][j].x][con[i][j].y] = cnt / con[i].size();
                }
                flag = true;
            }
        }
        if (flag) {
            answer++;
        }
    }
    cout << answer;
    return 0;
}