백준 16234번 인구 이동 ( C++ )

문제

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

해설

완탐으로 해결하는 간단한 문제

dfs의 실행 횟수보다는 인구이동이 발생했는지를 체크하는 변수가 있었으면 더 깔끔했을듯 하다.

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, l, r, uPerson, uCnt, ret, a[54][54], visited[54][54];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
vector<pair<int, int>> v;
 
void dfs(int y, int x)
{
  visited[y][x] = 1;
  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[ny][nx])
      continue;
    if (abs(a[ny][nx] - a[y][x]) < l || abs(a[ny][nx] - a[y][x]) > r)
      continue;
    uPerson += a[ny][nx];
    v.push_back({ny, nx});
    dfs(ny, nx);
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n >> l >> r;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> a[i][j];
    }
  }
 
  while (true)
  {
    uCnt = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (visited[i][j])
          continue;
 
        uPerson = a[i][j];
        v.clear();
        v.push_back({i, j});
 
        uCnt++;
        dfs(i, j);
        int person = uPerson / v.size();
        for (pair<int, int> p : v)
        {
          a[p.first][p.second] = person;
        }
      }
    }
    if (uCnt == n * n)
      break;
    ret++;
    fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
  }
  cout << ret;
}