[BOJ16234 C++] 인구이동

holy_joon·2023년 3월 26일
0

BOJ

목록 보기
12/13

이게 진정 골드 5 문제인건가.
같은 골드 5보다도 훨씬 어렵잖아!!!

내가 어렵게 푼 걸지도 . . . .

우선 이 문제는 참 재밌는게, 몇개의 연합이 생길지도 모르고, 각 연합마다 인구수를 n등분해서 뿌려주는 것

처음에 풀 때는 연합이 무조건 1개만 생기는 줄 알았는데 .. 그렇게 코드를 짜놓고 생각해보니 아니더라

n개의 연합이 생긴다면? -> vector를 써서 동적으로 연합을 저장하면 되지~

각 땅덩어리 [i][j] 마다 BFS를 돌려버린다.
그러면 국경이 열리는 것들이 한번에 싹 정리가 되고.. 하나의 연합이 만들어짐

그러면 그 연합을 vector에 처 넣고 ~ 인구수 조절을 때리면 된다.

아이디어는 진짜 쉬운데 구현이 너무 어려웠음 ㅜ

//
// Created by 신성준 on 2023/03/26.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <set>
#include <queue>
using namespace std;

int L, R, N;
int Arr[50][50];
vector<set<int>> coops;
int visited[50][50];

void check_coop2(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) {
            if (visited[i][j]) continue;
            visited[i][j] = 1;
            set<int> c;
            queue<int> q;
            q.push(i*N + j);
            int idx = i*N + j;
            while (!q.empty()) {
                idx = q.front();
                c.insert(idx);
                q.pop();

//                cout << idx << ' ' << endl;
                int x, y;
                x = idx / N;
                y = idx % N;

                if(x == 0){
                    int diff = abs(Arr[x][y] - Arr[x+1][y]);
                    if(diff >= L && diff <= R){
                        if(!visited[x+1][y]) {
                            q.push(N*(x+1)+y);
                            visited[x+1][y] = 1;
                        }
                    }
                }
                else if((x+1) == N){
                    int diff = abs(Arr[x][y] - Arr[x-1][y]);
                    if(diff >= L && diff <=R){
                        if(!visited[x-1][y]) {
                            q.push(N*(x-1)+y);
                            visited[x-1][y] = 1;
                        }
                    }
                }
                else{
                    int diff = abs(Arr[x][y] - Arr[x+1][y]);
                    if(diff >= L && diff <= R){
                        if(!visited[x+1][y]) {
                            q.push(N*(x+1) + y);
                            visited[x+1][y] = 1;
                        }
                    }
                    diff = abs(Arr[x][y] - Arr[x-1][y]);
                    if(diff >= L && diff <= R){
                        if(!visited[x-1][y]) {
                            q.push(N*(x-1) + y);
                            visited[x-1][y] = 1;
                        }
                    }
                }

                if(y == 0){
                    int diff = abs(Arr[x][y] - Arr[x][y+1]);
                    if(diff >= L && diff <= R){
                        if(!visited[x][y+1]) {
                            q.push(N*x + (y+1));
                            visited[x][y+1] = 1;
                        }
                    }
                }
                else if((y+1) == N){
                    int diff = abs(Arr[x][y] - Arr[x][y-1]);
                    if(diff >= L && diff <= R){
                        if(!visited[x][y-1]) {
                            q.push(N*x + (y-1));
                            visited[x][y-1] = 1;
                        }
                    }
                }
                else{
                    int diff = abs(Arr[x][y] - Arr[x][y+1]);
                    if(diff >= L && diff <= R){
                        if(!visited[x][y+1]) {
                            q.push(N*x + (y+1));
                            visited[x][y+1] = 1;
                        }
                    }
                    diff = abs(Arr[x][y] - Arr[x][y-1]);
                    if(diff >= L && diff <= R){
                        if(!visited[x][y-1]) {
                            q.push(N*x + (y-1));
                            visited[x][y-1] = 1;
                        }
                    }
                }

            }

            if(c.size() != 1){
                coops.push_back(c);
            }
        }

    }
}

int main() {
    ios::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 >> Arr[i][j];
        }
    }

    int cnt = 0;

    while(1){
        check_coop2();
        if(coops.size() == 0) break;
        for(int t = 0; t < coops.size(); t++){
            int population = 0;
            for(auto iter = coops[t].begin(); iter != coops[t].end(); iter++){
                int i = *iter / N;
                int j = *iter % N;
//                cout << i << " " << j << endl;
                population += Arr[i][j];
            }
//            cout << population << endl;
            population = population / coops[t].size();
//            cout << population << endl;

            for(auto iter = coops[t].begin(); iter != coops[t].end(); iter++){
                int i = *iter / N;
                int j = *iter % N;
                Arr[i][j] = population;
            }
        }
//        for(auto i = 0; i < N; i++){
//            for(auto j = 0; j < N; j++){
//                cout << Arr[i][j] << " ";
//            }
//            cout << endl;
//        }
        cnt++;
        coops.clear(); //연합 초기화
        fill_n(&visited[0][0], 50 * 50, 0); //visited 초기화
    }

//    for(auto i = 0; i < N; i++){
//        for(auto j = 0; j < N; j++){
//            cout << Arr[i][j] << " ";
//        }
//        cout << endl;
//    }
    cout << cnt;

}

과연 이후에 이 코드를 봤을 때 이해할 수 있을까.

profile
Deep Learning Image Processing

0개의 댓글