[BOJ/Python] 백준 2468번 - 안정 영역

백준 #2468 안전 영역

2468번: 안전 영역

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs(i, j, h, visited):
  q = deque()
  q.append((i, j))
  visited[i][j] = True
  cnt = 0
  while(q):
    cnt += 1
    v1, v2 = q.popleft()
    for dx, dy in (0, 1), (0, -1), (-1, 0), (1, 0):
      x, y = v1 + dx, v2 + dy
      if 0 <= x < n and 0 <= y < n and not visited[x][y] and height[x][y] > h:
        q.append((x, y))
        visited[x][y] = True

max_area = 0
for h in range(101):
  area = 0
  visited = [[False for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if height[i][j] > h and not visited[i][j]:
        bfs(i, j, h, visited)
        area += 1
  max_area = max(max_area, area)
  
print(max_area)

가능한 모든 물의 높이(1 이상 100 이하)의 경우를 모두 계산하며, 각 높이에서 영역이 몇 개 나오는지 bfs 탐색을 통해 구한다. 각 노드는 모두 시작 노드가 될 수 있는데, 이때 아직 방문하지 않은 노드만 시작 노드로 한다. 해당 노드에서 방문할 수 있는 곳을 모두 탐색하고 return 하면 한 영역을 모두 탐색한 것으로, 영역 + 1을 해준다. 이전 높이에서 구한 영역의 개수와 현재 구한 영역의 개수를 비교하여 더 큰 값을 저장한다.