[アルゴリズム解析]BOJ 16234人口移動

27052 ワード
boj BFS algorithm cpp simulation テキストリンク
今日の問題は白駿16234人口移転題です!
トニー9402の問題集で模擬問題の中の推薦問題を選んで解答しました!

BOJ 16234人口移転


N×Nサイズの地があり、地は1×格子に分ける.どの土地にも一つの国があり、r行c列の国にはA[r][c]名が住んでいる.隣国の間に境界線がある.すべての国×1サイズなので、すべての境界は正方形です.
今日から人口移転の日です.
人口移転は1日以内に以下の方法で行われ、以下の方法で人口移転が行われなくなるまで行われる.
  • 国境線を共有する両国の人口差がL名以上、R名以下であれば、両国が共有する国境線は今日開かれる.
  • 位の条件に従ってすべての境界線を開くと、人口の流れが開始される.
  • 国境線が開いていて、隣の1つの格子でしか移動できないなら、今日の1日でこの国は連合と呼ばれています.
  • 連合体を構成する各間の人口数は(連合体の人口数)/(連合体の個数)である.便利な小数点を捨てる.
  • 連盟を解散し、すべての国境線を閉鎖した.
    • 国ごとの人口数が与えられると、人口の流れが数日以内に発生する状況を知るプログラムを作成してください.

    にゅうしゅつりょく



    私の答え


    与えられた入力地図上で,連合可能な地域を探索し,連合に含まれる国の人口を再調整する過程を,連合が存在しないまで地図上でシミュレーション問題を繰り返す.
    最初は地図(0,0)から始まり,BFSを用いて連合可能な領域を探し,その後人口移動を開始したが,地図上には複数の独立した連合体が存在する可能性があるので,連合領域探索過程と人口移動過程は完全に分離すべきであることが分かった.
    「連合区域探索」&「人口移転」の過程を繰り返し、連合区域探索の結果、連合区域が発見されなければ、重複を停止し、人口移転回数を返還する.
    連合領域探索の過程で,連合国が左右上下に存在する座標を基準としてBFSを起動する.合併可能な国の座標を探し、その国の人口数を増やし、座標をベクトルとして格納します.
    BFSが終了するたびに,結合領域が見出され,この過程を(0,0)から(N−1,N−1)に繰り返した.
    この時、すべての国は一度だけ探求するだけです!連合に含まれる国家座標が左右上下どの方向に最初に検出されるか分からないため,アクセス配列によりすべての座標が1回のみ検出されることを保証した.
    私は複文全体でwhile(true)を使うのが好きではありませんが、他の人の解答では、ほとんどの人もwhile(true)を使って他の方法を探すべきです!

    コード#コード#

    #include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>

// BOJ 16234 인구이동, 시뮬레이션
using namespace std;

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

// 지도상에 존재하는 연합 - 연합에 포함되는 국가들 좌표와 인구 합
typedef struct unite{
    int totalPopulation;
    vector<pair<int, int>> countries;

    unite() {
        totalPopulation = 0;
        countries = vector<pair<int, int>>();
    }
}Unite;

// 지도상에 위치하는 연합 구하기
Unite bfs(vector<vector<int>> map, vector<vector<bool>> & visited, int i, int j, int N, int L, int R){
    Unite unite;
    queue<pair<int, int>> q;

    // BFS 시작점 저장 
    q.push(make_pair(i, j));
    visited[i][j] = true;

    while (!q.empty()){
        pair<int, int> location = q.front();
        q.pop();

        // 각 국가의 인구 수 누적 & 좌표 저장 
        unite.totalPopulation += map[location.first][location.second];
        unite.countries.push_back(location);

        for (int k = 0; k < 4; ++k) {
            int r = location.first + dy[k];
            int c = location.second + dx[k];

            if (r>=0 && r<N && c>=0 && c<N){ // 지도 범위 내
                int diff = abs(map[location.first][location.second] - map[r][c]); // 인구 차이

                if (diff >= L && diff <= R && !visited[r][c]){ // 조건에 맞으면 연합으로, 모든 좌표 한번씩만 방문
                    q.push(make_pair(r, c));
                    visited[r][c] = true;
                }
            }
        }
    }

    return unite;
}

int getMovigDays(vector<vector<int>> map, int N, int L, int R) {
    int moved = 0;

    while (true) {
        vector<Unite> unites;
        vector<vector<bool>> visited(N, vector<bool>(N, false));

        // 연합 지역을 탐색 
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {

                for (int k = 0; k < 4; ++k) {
                    int r = i + dy[k];
                    int c = j + dx[k];

                    if (r >= 0 && r < N && c >= 0 && c < N && !visited[r][c]) { // 지도 범위 내
                        int diff = abs(map[i][j] - map[r][c]);

                        if (diff >= L && diff <= R) { //시작 지점 발견하면 BFS 시작
                            Unite unite = bfs(map, visited, i, j, N, L, R);
                            unites.push_back(unite);  // 연합들을 알아낸 뒤
                        }
                    }
                }
            }
        }

        // 연합이 존재 하면 인구 이동 시작
        if (unites.size() > 0) {  
            moved++;
            for (int i = 0; i < unites.size(); ++i) {
                int avg = unites[i].totalPopulation / unites[i].countries.size();
                for (int j = 0; j < unites[i].countries.size(); ++j) {
                    pair<int, int> c = unites[i].countries[j];
                    map[c.first][c.second] = avg;
                }
            }

        } else {
            break;
        }
    }

    return moved;
}


int main() {
    int N, L, R;
    cin>>N>>L>>R;

    vector<vector<int>> map(N, vector<int>(N,0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin>>map[i][j];
        }
    }

    int answer = getMovigDays(map, N, L, R);

    cout<<answer;

    return 0;
}
    TIL - CodeKata(4)
    intro & setup