백준 2468번 안전 영역( C++ )

문제

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

2468번: 안전 영역

 

해설

집단의 수를 구하고 집단이 가장 많아질때를 구하는 문제

dfs / bfs 둘다 상관없어 좀 더 간단한 dfs선택

시간을 줄이기 위해 가장작은수 -1 ~ 가장큰수까지 돌며 집단확인

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, ret, num;
int mp[104][104];
int visited[104][104];
int minNum = 1;
int maxNum = 100;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
 
void dfs(int y, int x, int num)
{
  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] == 1 || mp[ny][nx] <= num)
      continue;
    dfs(ny, nx, num);
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> num;
      mp[i][j] = num;
      if (num < minNum)
        minNum = num;
      else if (num > maxNum)
        maxNum = num;
    }
  }
 
  for (int numNow = minNum - 1; numNow < maxNum; numNow++)
  {
    fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
    int count = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (mp[i][j] > numNow && visited[i][j] == 0)
        {
          dfs(i, j, numNow);
          count++;
        }
      }
    }
    if (count > ret)
      ret = count;
  }
 
  cout << ret;
}