My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 16234 인구 이동

백준 16234 인구 이동

2022년 11월 28일

2022년 11월 28일

cpp, 탐색

문제

문제

풀이

풀이

탐색을 이용해 연합국의 존재 여부와 존재할 경우 이동해야할 인구 수를 저장한 후, 인구 이동을 진행해준다.

코드

코드

#include <bits/stdc++.h>

using namespace std;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<pair<int,int>>> vvpii;
int n,l,r;
int world[52][52];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
bool vis[52][52];
vvpii unites;
int find_unite(int x, int y){
    vpii unite; // 연합국의 좌표를 담음
    queue<pair<int,int>> q;
    int cnt = world[x][y];
    q.push({x,y});
    vis[x][y] = true;
    unite.push_back({x,y});
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(int dir=0; dir<4; dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if(nx<0||ny<0||nx>=n||ny>=n) continue;
            if(vis[nx][ny]) continue;
            int diff = abs(world[cur.first][cur.second] - world[nx][ny]);
            if(diff < l || diff > r) continue;
            unite.push_back({nx,ny});
            q.push({nx,ny});
            vis[nx][ny] = true;
            cnt += world[nx][ny];
        }
    }
    if(unite.size() == 1) return 0;
    unites.push_back(unite);
    return cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l >> r;
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cin >> world[i][j];
    int days = 0;
    while(1){
        vector<int> score; // 연합들의 총 인구 수를 보관
        int cnt;
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j){
                if(vis[i][j]) continue;
                if(cnt = find_unite(i,j)) score.push_back(cnt);
            }
        if(score.empty()) break; // 연합을 찾지 못하면 break
        // 인구 이동
        for(int i=0; i<unites.size(); ++i){
            int total = score[i]/unites[i].size();
            for(auto c:unites[i])
                world[c.first][c.second] = total;
            unites[i].clear();
        }
        days++;
        for(int i=0; i<n; ++i)
            fill(vis[i],vis[i]+n,false);
        unites.clear();
    }
    cout << days;
}

결과

결과

Copyright © 2024 Hyunghoon Kim