BOJ
BOJ::16234 인구 이동
BOJ Gold 5
BOJ::16234 인구 이동
- Link : BOJ::16234
- Level : Gold 5
- tag : bfs
시사점
이해(4)
- n(맵의 사이즈), L, R이 주어집니다.
- map의 원소가 주어집니다.
- 매년 인구이동이 가능한 국가들끼리 인구이동을 합니다.
- 인접한 국가간 인구차이가 L이상 R이하인 경우 해당 국가들을 인구이동이 가능하다고 표현합니다.
- 이렇게 인구이동이 가능한 국가끼리 국경을 개방합니다.
- 따라서, 국경을 다시 닫기 전에,
- 개방한 인접국 모두의 인구수를 sum / size 로 평균을 구해 동일한 값을 가지게 합니다.
- 이렇게 시뮬레이션을 돌려서, 인구이동이 최대 몇 해동안 발생하는지 출력합니다.
설계, 손 코딩(2)
- 손으로 중심이 되는 코드를 구현합니다.
시간 복잡도
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(8)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.
#include<bits/stdc++.h>
#define endl '\n'
#define se second
#define fi first
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int MAXN = 50;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
int n, L, R;
int a[MAXN][MAXN];
bool seen[MAXN][MAXN];
queue<pair<int,int> >q;
void input(){
cin >> n >> L >> R;
rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
}
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=n);}
bool bfs(int sx, int sy){
queue<pair<int,int> > bq;
int sum = 0;
bool ret = false;
q.push({sx, sy});
seen[sx][sy]= true;
while(!q.empty()){
int x = q.front().fi, y = q.front().se; q.pop();
sum += a[x][y];
bq.push({x, y});
rep(i, 0, 4){
int nx = x+dx[i], ny = y+dy[i];
if(over(nx, ny) || seen[nx][ny]) continue;
int diff = abs(a[nx][ny] - a[x][y]);
if(L<= diff && diff <= R){
ret |= true;
seen[nx][ny] = true;
q.push({nx, ny});
}
}
}
if(bq.size() > 1){
int mean = sum / (int) bq.size();
while(!bq.empty()){
int x = bq.front().fi, y = bq.front().se; bq.pop();
a[x][y] = mean;
}
}
return ret;
}
int process(){
input();
int t = 0;
while(true){
bool found = false;
memset(seen, false, sizeof(seen));
rep(i, 0, n){
rep(j, 0, n){
if(!seen[i][j]){
found |= bfs(i, j);
}
}
}
if(!found) return t;
t++;
}
return -1;
}
int main(){
#ifdef DEBUG
freopen("input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << process() << endl;
return 0;
}