(DFS) 백준 2468번 안전 영역

import sys
import copy
sys.setrecursionlimit(10000)

N = int(input())
dfs_list = []

for _ in range(N):
    dfs_list.append(list(map(int, input().split())))

for k in range(1, N):
    max_num = max(max(dfs_list[k-1]), max(dfs_list[k])) # 주어진 리스트의 최대 값 (최대 높이)을 구하기 위해 max_num에 저장.

def dfs(row, column, height):
    if row < 0 or row >= N or column < 0 or column >= N: # 범위를 벗어날 경우 즉시 종료
        return False

    if copy_list[row][column] <= height: # 현재 강우량보다 낮으면, 즉 물에 잠기는 부분일 경우 계산할 필요 없으므로 종료
        return False

    copy_list[row][column] > height: # 안전 영역일 경우
    copy_list[row][column] = height # 영역을 검사했음을 표시. 어차피 height이하면 검사 안하므로 height로 놓아줬다.

	# 역시 동서남북 검사하면서 전부 방문한다.
    dfs(row+1, column, height)
    dfs(row-1, column, height)
    dfs(row, column+1, height)
    dfs(row, column-1, height)

        return True # 방문이 끝나면 리턴 True

answer = []

for i in range(max_num):   # 0부터 최대 높이만큼 강우량을 조건으로 한다. (어차피 다 잠기면 0이므로 최대 값이 안된다.)
                           # 물에 안잠길 수도 있으므로 0부터 이다. (높이가 1부터 시작이므로)
                           # 모든 곳이 다 물에 잠길 수 있으므로 최대 높이의 +1 까지 계산한다.
    copy_list = copy.deepcopy(dfs_list) # copy_list = dfs_list[:]의 깊은 복사는 1차원 배열만 복사된다. 2차원 배열일 경우 안된다. 각 강우량만큼 초기화된 배열이 필요하므로 매번 초기화 해준다.
    count = 0 # 각 비의 양 만큼 영역의 개수를 구하는 count 배열, 역시 매번 초기화
    for x in range(N):
        for y in range(N):
            response = dfs(x, y, i) # 지점의 좌표와 현재 강우량을 dfs에 넣는다.
            if response == True: # return이 True일 경우 각 영역에 대한 dfs 탐색이 끝났으므로 count의 값을 증가시켜준다.
                count += 1

    answer.append(count) # 각 강수량마다 count의 갯수를 answer 리스트에 저장

print(max(answer)) # answer 리스트에서 최댓 값이 정답이 된다.