[탐색/BFS] 백준 2468 안전 영역 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2468번: 안전 영역

 

 

 

2. 문제 풀이

 비에 침수되지 않는 구역(안전구역)의 최대 개수를 구하는 문제입니다. 강수량은 높이 1부터 100까지 주어집니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 침수되는 높이가 1 ~ 100일 때의 안전 구역의 수를 BFS탐색으로 구합니다.

 

 

 

3. 코드

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

# 입력
N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

# 높이 1 ~ 100까지 BFS 탐색
direction = [(1,0), (-1,0), (0,1), (0,-1)]
res = 0  # 안전 구역
for high in range(0, 101):
    visited = [[False]*N for _ in range(N)]
    queue = deque([])
    cnt = 0  # 안전구역

    for i in range(N):
        for j in range(N):
            if not visited[i][j] and board[i][j] > high:
                cnt += 1
                queue.append((i, j))
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in direction:
                        nx, ny = x+dx, y+dy
                        if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and board[nx][ny] > high:
                            visited[nx][ny] = True
                            queue.append((nx, ny))
    # print(high, cnt)
    res = max(res, cnt)
print(res)

 입력받을 때, 가장 낮은 높이와 가장 높은 높이를 체크해서 해당 영역만 BFS 탐색할 수도 있습니다. 저는 어차피 테스트 케이스 중에 1 ~ 100까지 다 탐색하는 경우를 감안해서 시간 제한으로 해뒀을 거 같아 모두 탐색했습니다.

 비가 아예 오지 않을 경우(0)도 있으므로, 0부터 100까지 강수량의 높이를 순회합니다. (0, 0)부터 (N-1, N-1)까지 강수량의 높이 이상인 안전구역을 체크하고, 안전구역이면 cnt +1하고 그 주변에 강수량보다 높은 데가 있는지 탐색합니다.