2468. 안전 영역

탐색만 하면 되니까 dfs bfs 모두 가능하다. 높이 보다 높으면 탐색 시작 점이 될 수 있고 그 시작점에서 그래프 탐색을 시작한다.

 

 

JavaScript bfs

const fs = require("fs")
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n")
const n = +input[0]
const board = input.slice(1).map((e) => e.split(" ").map((e) => +e))
const max = Math.max(...board.flat())
let dx = [0, 0, 1, -1],
  dy = [1, -1, 0, 0]
function bfs(x, y, h, visited) {
  const q = [[x, y]]
  while (q.length) {
    const [x, y] = q.shift()
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i],
        ny = y + dy[i]
      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
      if (board[nx][ny] > h && !visited[nx][ny]) {
        visited[nx][ny] = true
        q.push([nx, ny])
      }
    }
  }
}
let i = 0,
  ans = 0
while (i <= max) {
  let cnt = 0
  const visited = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => false)
  )
  for (let x = 0; x < n; x++) {
    for (let y = 0; y < n; y++) {
      if (!visited[x][y] && board[x][y] > i) {
        bfs(x, y, i, visited)
        cnt += 1
      }
    }
  }
  i++
  ans = Math.max(cnt, ans)
}
console.log(ans)

 

 

python dfs

import sys
sys.setrecursionlimit(10**9)
input =sys.stdin.readline
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
_min, _max = min(map(min, board)), max(map(max, board))
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = 0
i = 0 
def dfs(x,y,i):
  if x < 0 or x >= n or y < 0 or y >= n:
        return False
  if board[x][y] > i and not visited[x][y]:
    visited[x][y] = True
    for k in range(4):
      dfs(x+dx[k], y+dy[k], i)
    return True
while i <= _max:
  cnt = 0 
  visited = [[0] * n for _ in range(n)]
  for x in range(n):
    for y in range(n):
      if not visited[x][y] and dfs(x,y,i):
        cnt += 1
  ans = max(ans, cnt)
  i+=1
print(ans)