백준 2468번 안전 영역

문제:
어떤 지역의 높이 정보가 주어졌을 때, 비가 왔을 때 물에 잠기지 않는 안전한 영역의 최대 개수를 구하는 문제.
비의 높이는 문제에 주어지지 않기 때문에, 가능한 모든 비의 높이에 대해 시뮬레이션해야 함.

입력:
첫째 줄에 지역의 크기 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개의 줄에 각 지점의 높이 정보가 주어진다. (1 ≤ 높이 ≤ 100)

출력:
비의 높이를 조절했을 때, 물에 잠기지 않는 영역(연결된 구역)의 최대 개수를 출력한다.

from collections import deque

dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x,y,h):
    q = deque()
    q.append((x,y))
    visited[y][x] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

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

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
max_len = max(map(max, graph))
result = 0

for h in range(0, max_len+1):
    count = 0
    visited = [[False] * n for _ in range(n)]
    for y in range(n):
        for x in range(n):
            if graph[y][x] > h and not visited[y][x]:
                bfs(x, y, h)
                count += 1
    result = max(result, count)

print(result)

맨 위로 이동