[백준] 16234번 인구 이동 C++ 코드

코드

#include <bits/stdc++.h>
using namespace std;
int n,lo,hi,te[52][52],visited[52][52],human,day;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
vector<pair<int,int>> v;

void dfs(int x, int y) {
  for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx <0 || nx >= n || ny >= n || ny < 0 || visited[nx][ny]) continue;
    if(abs(te[nx][ny] - te[x][y]) >= lo && abs(te[nx][ny] - te[x][y]) <= hi) {
      visited[nx][ny] = 1;
      v.push_back({nx,ny});
      human += te[nx][ny];
      dfs(nx, ny);
    }
  }
}

int main() {
  cin >> n >> lo >> hi;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cin >> te[i][j];
    }
  }
  while(1){
    bool ok = false;
    memset(visited,0,sizeof(visited));
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(!visited[i][j]) {
          v.clear();
          visited[i][j] = 1;
          v.push_back({i,j});
          human = te[i][j];
          dfs(i,j);
          if(v.size() == 1) continue;
          for(pair<int,int> b : v) {
            te[b.first][b.second] = human / v.size();
            ok = true;
          }
        }
      }
    }
    if(!ok) break;
    day++;
  }
  cout << day << '\n';
  return 0;
}

dfs로 연결되는 부분을 확인한 후, 인구 분배를 해준다. 인구 분배가 된다면 flag 변수를 true로 변경한다. 만약 변경이 없다면 반복문을 탈출하고 몇 번 이동이 일어났는지 출력하면 된다. v.size()가 1일 때 continue 하는 이유는, 영역이 1인 경우에는 이동이 일어나지 않기 때문이다.