[백준] 2468번: 안전 영역 - c++

안전 영역

문제

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제

문제 정의

이 문제에서 N의 범위가 2이상 100 이하의 정수이고, 높이가 1이상 100이하의 정수이므로 높이를 하나씩 탐색하면서 풀었다.

반복문으로 1에서 100사이의 정수를 받아 각 정수(높이)에서의 안전영역에 관해 하나 씩 dfs를 돌리며 연결요소의 개수를 찾았다.

이 문제도 하나의 높이에 대한 안전영역(연결요소)의 개수를 구하는 문제이므로 dfs로 풀이했다.

#include<bits/stdc++.h>
using namespace std;
int n, adj[104][104], visited[104][104];
int res = 1;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};

// dfs
void dfs(int y, int x, int h) {
  visited[y][x] = 1;
  for (int i = 0; i < 4; i++) {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if (ny<0 || ny>=n || nx<0 || nx>=n || visited[ny][nx]) continue;
    if (adj[ny][nx] <= h) continue;
    dfs(ny, nx, h);
  }
  return;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> adj[i][j];
    }
  }
  for (int i = 1; i < 101; i++)  {
    int cnt = 0;
    memset(visited, 0, sizeof(visited));
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < n; b++) {
        if(adj[a][b] > i && !visited[a][b]) {
          dfs(a, b, i);
          cnt++;
        }
      }
    }
    res = max(res, cnt);
  }
  cout << res << "\n";
}