OJ 16234 : 인구 이동 - C++
인구 이동
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 12:02 ~ 12:27
int N, L, R, ans;
int board[55][55];
int vis[55][55];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> L >> R;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cin >> board[i][j];
while(true)
{
// BFS를 돌면서 인구수를 비교해서 L이상 R이하면 큐에 넣자
bool flag = false;
for(int i=0;i<N;i++)
fill(vis[i], vis[i]+N, false);
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(vis[i][j]) continue;
queue<pair<int,int>> q;
vector<pair<int,int>> change;
q.push({i,j});
change.push_back({i,j});
vis[i][j] = true;
int sum=board[i][j];
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
int diff = abs(board[cur.first][cur.second] - board[ny][nx]);
if(vis[ny][nx] or diff<L or diff >R) continue;
q.push({ny,nx});
vis[ny][nx] = true;
sum += board[ny][nx];
change.push_back({ny,nx});
}
}
/* 이동이 있었다면 끝내면 안됨 */
if(change.size() >= 2) flag = true;
int avg = sum/change.size();
for(int j=0;j<change.size();j++)
{
auto cur = change[j];
board[cur.first][cur.second] = avg;
}
}
}
/* 이동한 나라가 없으므로 종료 */
if(!flag) break;
ans++;
}
cout << ans;
return 0;
}
- 로직
모든 점
에 대해서 BFS 수행
BFS
를 돌면서 인접한 점
과 인구수 차이
가 L 이상 R이하
이면 큐
에넣고 계속 수행
인구 이동
이 없으면 종료
Author And Source
이 문제에 관하여(OJ 16234 : 인구 이동 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-16234-인구-이동-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #include <map> #define ll long long using namespace std; // 12:02 ~ 12:27 int N, L, R, ans; int board[55][55]; int vis[55][55]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> L >> R; for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> board[i][j]; while(true) { // BFS를 돌면서 인구수를 비교해서 L이상 R이하면 큐에 넣자 bool flag = false; for(int i=0;i<N;i++) fill(vis[i], vis[i]+N, false); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(vis[i][j]) continue; queue<pair<int,int>> q; vector<pair<int,int>> change; q.push({i,j}); change.push_back({i,j}); vis[i][j] = true; int sum=board[i][j]; while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=N or ny>=N) continue; int diff = abs(board[cur.first][cur.second] - board[ny][nx]); if(vis[ny][nx] or diff<L or diff >R) continue; q.push({ny,nx}); vis[ny][nx] = true; sum += board[ny][nx]; change.push_back({ny,nx}); } } /* 이동이 있었다면 끝내면 안됨 */ if(change.size() >= 2) flag = true; int avg = sum/change.size(); for(int j=0;j<change.size();j++) { auto cur = change[j]; board[cur.first][cur.second] = avg; } } } /* 이동한 나라가 없으므로 종료 */ if(!flag) break; ans++; } cout << ans; return 0; }
- 로직
모든 점
에 대해서BFS 수행
BFS
를 돌면서인접한 점
과인구수 차이
가L 이상 R이하
이면큐
에넣고계속 수행
인구 이동
이없으면 종료
Author And Source
이 문제에 관하여(OJ 16234 : 인구 이동 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-16234-인구-이동-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)