백준 | 안전 영역

백준 안전 영역

강수량의 탐색 범위(h)는 비가 오지 않는 경우(0)부터, 주어진 지형의 최대 높이(max_height)까지이다.

각 강수량에 대한 안전 영역의 개수를 구하기 위해 BFS로 탐색했고, visited라는 배열을 활용해 다음 조건을 만족하는 영역을 하나의 영역으로 묶었다.

[1] 아직 방문하지 않은 영역: visited[i][j] == False
[2] 탐색 중인 강수량보다 높이가 높은 영역: graph[i][j] > h

이렇게 모든 영역에 대한 탐색을 수행하면, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 구할 수 있다.

import sys
from collections import deque

# 입력
n = int(sys.stdin.readline().strip())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 방향 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최대 높이
max_height = max(map(max, graph))

# BFS
def bfs(x, y, h, visited):
    queue = deque([(x, y)])
    visited[x][y] = True
    
    while queue:
        cx, cy = queue.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > h and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

# 물에 잠기지 않는 안전한 영역의 최대 개수
max_safe_area = 0

for h in range(max_height + 1):
    visited = [[False] * n for _ in range(n)]
    safe_area = 0

    for i in range(n):
        for j in range(n):
            if graph[i][j] > h and not visited[i][j]:
                    bfs(i, j, h, visited)
                    safe_area += 1

    max_safe_area = max(max_safe_area, safe_area)

# 출력
print(max_safe_area)