[백준 2468] 안전영역

1. 문제

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

2. 접근 방법

일단 비가 얼만큼 내렸을 때 안전한 영역이 몇개가 되는지를 구하기 위해서 비가 올 수 있는 높이를 구해야합니다.

저는 최소 높이 -1 ~ 최대 높이 만큼을 비가 올 수 있는 경우로 지정했습니다.

최소 높이 -1 부터 시작한 이유는 "아무 지역도 물에 잠기지 않을 수도 있다."라고 명시되어 있기 때문입니다.

 

비가 음수만큼 내린다느 것은 사실 말이 안되긴 하지만,

내리는 비의 높이보다 board에 있는 숫자가 더 클 경우를 구하는 것이 목표이기 때문에 그냥 최소 높이 -1 로 해줬습니다.

 

 

그렇게 비의 높이를 정하고 나면, 비의 높이를 기준으로 영역을 나눠줘야합니다.

 

영역의 정보를 얻기 위해서 bfs를 사용하면 됩니다.

 

3. 코드

python

from collections import deque


def bfs(height):
    global N, board
    visited = [[False]*N for _ in range(N)]
    cnt = 0
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    for y in range(N):
        for x in range(N):
            if not visited[y][x] and board[y][x] > height:
                visited[y][x] = True
                land = deque()
                land.append((x, y))

                while land:
                    nx, ny = land.popleft()
                    for i in range(4):
                        tx, ty = nx + dx[i], ny + dy[i]
                        if 0 <= tx < N and 0 <= ty < N and not visited[ty][tx]:
                            visited[ty][tx] = True
                            if board[ty][tx] > height:
                                land.append((tx, ty))
                cnt += 1
    return cnt


N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
answer = 0
max_val = 0
min_val = 1e9
for i in range(N):
    max_val = max(max_val, max(board[i]))
    min_val = min(min_val, min(board[i]))

for rain_height in range(min_val-1, max_val+1):
    answer = max(answer, bfs(rain_height))
print(answer)

4. 마치며

마치며~!