-
[백준] 16234 - 인구 이동Algorithm 문제 2019. 7. 23. 14:40
https://www.acmicpc.net/problem/16234
간단한 탐색 문제이고 queue를 이용한 dfs로 풀었다.
<C++ 코드>
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <cstdio>#include <stdlib.h>#include <string.h>#include <queue>using namespace std;int country[50][50];int vis[50][50];int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};int main(){int n, l, r;scanf("%d %d %d", &n, &l, &r);for(int i=0; i<n; i++){for(int j=0; j<n; j++){scanf("%d", &country[i][j]);}}int re = 0;while(true){bool move = false;memset(vis, 0, sizeof(vis));for(int i=0; i<n; i++){for(int j=0; j<n; j++){if(!vis[i][j]){vis[i][j] = true;queue<pair<int, int> > q;vector<pair<int, int> > v;int sum = country[i][j];q.push(make_pair(i, j));v.push_back(make_pair(i, j));while(!q.empty()){int y = q.front().first, x = q.front().second;q.pop();for(int d=0; d<4; d++){int ay = y + dy[d], ax = x + dx[d];if(ay >= 0 && ay < n && ax >= 0 && ax < n && !vis[ay][ax] && abs(country[ay][ax] - country[y][x]) >= l && abs(country[ay][ax] - country[y][x]) <= r){vis[ay][ax] = true;q.push(make_pair(ay, ax));v.push_back(make_pair(ay, ax));sum += country[ay][ax];}}}if(v.size() > 1){int avg = sum / v.size();for(int k=0; k<v.size(); k++){country[v[k].first][v[k].second] = avg;}move = true;}}}}if(!move) break;else re++;}printf("%d", re);return 0;}cs 'Algorithm 문제' 카테고리의 다른 글
[백준] 17142 - 연구소 3 (0) 2019.07.28 [백준] 17143 - 낚시왕 (0) 2019.07.25 [백준] 15683 - 감시 (0) 2019.07.22 [백준] 14889 - 스타트와 링크 (0) 2019.07.17 [백준] 14500 - 테트로미노 (0) 2019.07.15