이번 문제는 깊이우선탐색을 통해 해결하였다. 처음에는 공간 복잡도를 최대한 줄이기 위해서 방문처리 리스트를 사용하지 않고 구현해보려고 했다. 이 방법을 위해 매 반복마다 높이의 최솟값을 구한 뒤에 dfs함수에서 거쳐가는 위치의 높이에서 최솟값을 빼주는 방식으로 해보기로 했지만 이 방법은 재귀 호출의 조건에 걸려 방문하지 않은 구역의 높이는 그대로 유지되기 때문에 맞지 않는 접근이었다.

그래서 결국은 방문처리 리스트를 사용하기로 하였다. 우선 최소한으로 반복하기 위해서 높이의 최솟값과 최댓값을 구한 뒤에 물에 잠기는 기준을 최솟값-1부터 최댓값까지 1씩 늘려가며 그때 그때의 가라앉지 않은 영역의 갯수를 리스트에 저장하고 최종적으로 리스트에서 가장 큰 값을 출력하도록 작성하였다. 기준의 범위를 최솟값-최댓값으로 지정했을 때는 만약 모든 높이가 같을 경우에 무조건 영역의 최대 갯수가 0이 되기 때문에 모든 땅이 가라앉지 않은 경우를 추가하기 위해 (최솟값-1)-최댓값으로 지정하였다.

dfs()함수의 경우에는 4가지 방향으로 나아가며 방문 전이고 기준 높이보다 높을 경우에만 재귀호출 하는 방식으로 작성하였다.

• 재귀 제한을 늘려준다.
• dfs함수를 y, x, depth를 인자로 갖도록 선언한다.
  -> visited[y][x]를 True로 갱신하여 방문처리해준다.
  -> 4가지 방향에 대한 정보를 dy, dx 리스트에 짝지어 담는다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny, nx가 n보다 작고, area[ny][nx]가 depth보다 크고, visited[ny][nx]가 False일 경우, dfs(ny, nx, depth)를 재귀호출한다.
• n을 입력받는다.
• 지역의 높이를 저장할 리스트 area를 선언한다.
• 지역의 최소 높이를 저장할 변수 mn을 가장 큰 수로 선언한다.
• 지역의 최대 높이를 저장할 변수 mx을 0으로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> area를 입력한다.
  -> mn을 area[i]의 최솟값과 mn 중 더 작은 값으로 갱신한다.
  -> mx를 area[i]의 최댓값과 mx 중 더 큰 값으로 갱신한다.
• 영역의 갯수들을 저장할 리스트 results를 선언한다.
• mn-1부터 mx까지 반복하는 i에 대한 for문을 돌린다.
  -> 방문처리에 사용할 리스트 visited를 n*n개의 False로 채운다.
  -> 영역의 개수를 카운팅할 변수 cnt를 0으로 선언한다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> n번 반복하는 k에 대한 for문을 돌린다.
  ---> 만약 area[j][k]가 mn보다 크고, visited[ny][nx]가 False일 경우,
  ----> dfs(i, j, i)를 호출한다.
  ----> cnt를 1 증가시킨다.
  -> results에 cnt를 넣는다.
• results의 최댓값을 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x, depth):
    visited[y][x]=True
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<n and nx<n and area[ny][nx]>depth and visited[ny][nx]==False:
            dfs(ny, nx, depth)
n=int(input())
area=[]
mn=sys.maxsize
mx=0
for i in range(n):
    area.append(list(map(int, input().split())))
    mn=min(min(area[i]), mn)
    mx=max(max(area[i]), mx)
results=[]
for i in range(mn-1, mx+1):
    visited=[[False]*n for _ in range(n)]
    cnt=0
    for j in range(n):
        for k in range(n):
            if area[j][k]>i and visited[j][k]==False:
                dfs(j, k, i)
                cnt+=1
    results.append(cnt)
print(max(results))