[백준 2468] 안전 영역 (C#, C++) - soo:bak

문제 링크

2468번 - 안전 영역

설명

비의 높이가 주어졌을 때 그 높이 이하의 칸이 모두 잠긴다고 가정하면, 물에 잠기지 않은 칸들이 상하좌우로 이어진 영역들이 생깁니다. 가능한 모든 비의 높이에 대해 안전 영역의 개수를 구하고, 그중 최댓값을 찾는 문제입니다.

접근법

비의 높이를 0부터 지역에서 가장 높은 곳까지 하나씩 가정해 보며, 그때 물에 잠기지 않은 칸들로 이루어진 연결 요소의 개수를 셉니다.

각 높이마다 아직 방문하지 않았고 물에 잠기지 않은 칸에서 탐색을 시작하면 하나의 안전 영역을 모두 방문할 수 있습니다. 이렇게 영역 수를 세어 매번 최댓값을 갱신하면 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static readonly int[] dx = { -1, 1, 0, 0 };
  static readonly int[] dy = { 0, 0, -1, 1 };

  static void Main() {
    int n = int.Parse(Console.ReadLine()!);
    int[,] board = new int[n, n];
    int maxHeight = 0;

    for (int i = 0; i < n; i++) {
      var row = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
      for (int j = 0; j < n; j++) {
        board[i, j] = row[j];
        if (row[j] > maxHeight)
          maxHeight = row[j];
      }
    }

    int answer = 0;

    for (int rain = 0; rain <= maxHeight; rain++) {
      bool[,] visited = new bool[n, n];
      int count = 0;

      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (visited[i, j] || board[i, j] <= rain)
            continue;

          count++;
          var queue = new Queue<(int x, int y)>();
          queue.Enqueue((i, j));
          visited[i, j] = true;

          while (queue.Count > 0) {
            var cur = queue.Dequeue();
            for (int dir = 0; dir < 4; dir++) {
              int nx = cur.x + dx[dir];
              int ny = cur.y + dy[dir];

              if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
              if (visited[nx, ny] || board[nx, ny] <= rain)
                continue;

              visited[nx, ny] = true;
              queue.Enqueue((nx, ny));
            }
          }
        }
      }

      if (count > answer)
        answer = count;
    }

    Console.WriteLine(answer);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  vector<vector<int>> board(n, vector<int>(n));
  int max_height = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> board[i][j];
      max_height = max(max_height, board[i][j]);
    }
  }

  int answer = 0;

  for (int rain = 0; rain <= max_height; rain++) {
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    int count = 0;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (visited[i][j] || board[i][j] <= rain)
          continue;

        count++;
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = true;

        while (!q.empty()) {
          auto cur = q.front();
          q.pop();

          for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
              continue;
            if (visited[nx][ny] || board[nx][ny] <= rain)
              continue;

            visited[nx][ny] = true;
            q.push({nx, ny});
          }
        }
      }
    }

    answer = max(answer, count);
  }

  cout << answer << "\n";

  return 0;
}