0. 문제

문제 링크

1. 풀이

전형적인 그래프 탐색 문제인데, 그래프 배열의 크기가 최대 100*100, 높이의 범위 역시 최대 100이므로 $O(N^3)$의 시간 복잡도로도 통과할 수 있다.

따라서 가능한 모든 높이에 대해서 BFS를 이용해 안전 영역을 구해본 후 그 중 영역의 수가 최대가 되는 경우를 출력하면 된다.

import sys
from collections import deque

MAXN = 101

graph = [[0 for j in range(MAXN)] for i in range(MAXN)]
n = int(sys.stdin.readline())

def bfs(row: int, col: int, height: int, check=[[]]):
    global n
    dr = [-1, 0, 1, 0]
    dc = [0, -1, 0, 1]

    dq = deque()
    dq.append((row, col))
    check[row][col] = True
    
    while len(dq) > 0:
        cur_row, cur_col = dq.popleft()
        for i in range(4):
            nr = cur_row + dr[i]
            nc = cur_col + dc[i]
    
            if (
                nr < 0
                or nr >= n
                or nc < 0
                or nc >= n
                or graph[nr][nc] <= height
                or check[nr][nc]
            ):
                continue
    
            check[nr][nc] = True
            dq.append((nr, nc))


max_rain_height = 0
for i in range(n):
    li = list(map(int, sys.stdin.readline().split()))
    cur_max_height = max(li)
    max_rain_height = (
        max_rain_height if max_rain_height > cur_max_height else cur_max_height
    )
    for j in range(n):
        graph[i][j] = li[j]

ans = 0
for height in range(1, max_rain_height):
    check = [[False for j in range(MAXN)] for i in range(MAXN)]
    island = 0
    for row in range(n):
        for col in range(n):
            if graph[row][col] > height and not check[row][col]:
                bfs(row, col, height, check)
                island += 1

    ans = max(ans, island)


print(ans if ans > 0 else 1)

3. 결과