안전영역 -2468 (DFS)

입력

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

출력

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

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,1,-1]

def dfs(x,y,h):
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if (0<=nx<n) and (0<=ny<n) and not visit[nx][ny] and graph[nx][ny] > h:
      visit[nx][ny] = True
      dfs(nx,ny,h)

n= int(input())
graph=[list(map(int,input().split())) for _ in range(n)]

max_safe = 0
for h in range(max(map(max,graph))):
  visit = [[False] * n for _ in range(n)]
  cnt=0
  for i in range(n):
    for j in range(n):
      if not visit[i][j] and graph[i][j] > h:
        visit[i][j] = True
        dfs(i,j,h)
        cnt+=1
  if max_safe < cnt : max_safe = cnt
print(max_safe)