BOJ 16234: 인구 이동 작성일 2020-03-02 https://www.acmicpc.net/problem/16234 3월동안 210문제 풀기 (6/210) DFS 두번 돌리는 문제, DFS 한번 돌릴때 합이랑 개수 구하고, 두번째에서 기록하면 됨. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <bits/stdc++.h> using namespace std; int N, L, R; vector<vector<int>> arr, visit; const int dx[4] = {0,0,1,-1}; const int dy[4] = {1,-1,0,0}; inline bool bound(int x, int y) { return x >= 0 && x < N && y >= 0 && y < N; } void go(int x, int y, int& cnt, int& num) { visit[x][y] = 1; cnt = 1, num = arr[x][y]; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!bound(nx,ny) || visit[nx][ny]) continue; int diff = abs(arr[x][y] - arr[nx][ny]); if(diff < L || diff > R) continue; int subCnt, subNum; go(nx,ny, subCnt, subNum); cnt += subCnt, num += subNum; } } void fill(int x, int y, int v) { if(v != -1) arr[x][y] = v; visit[x][y] = 2; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!bound(nx,ny) || visit[nx][ny] != 1) continue; fill(nx,ny,v); } } int main() { scanf("%d %d %d", &N, &L, &R); arr = vector<vector<int>>(N, vector<int>(N)); visit = vector<vector<int>>(N, vector<int>(N)); for(int i =0; i < N; i++) for(int j = 0; j < N; j++) scanf("%d", &arr[i][j]); int gen = 0; while(1) { bool flag = 0; for(int i =0; i < N; i++) for(int j = 0; j < N; j++) if(!visit[i][j]) { int cnt, num; go(i,j,cnt,num); if(cnt > 1) { fill(i,j,num/cnt); flag = true; } else fill(i,j,-1); } if(!flag) break; gen++; for(int i =0; i < N; i++) for(int j = 0; j < N; j++) visit[i][j] = 0; } printf("%d",gen); }