[BOJ][python] 2468. 안전 영역

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

2468번: 안전 영역

---

💡IDEA

BFS를 사용하는 문제이다.

일정 높이만큼 비가 내렸을 때, 잠기지 않는 영역의 개수의 최대값을 구하는 문제이다.

높이는 입력받은 높이 값들 중 가장 작은 값부터 시작하여 가장 큰 값까지 bfs 함수를 수행하며 개수를 센다.

가장 작은 값 min_height와 가장 큰 값 max_height는 파이코닉한 방법으로 구할 수 있다는 점을 유의한다.

bfs에서는 일정 높이보다 높은, 즉 안전한 높이인 경우에 상하좌우로 연결된 부분을 확인한다. bfs를 수행한 후 개수를 카운트해주어 이 개수 중 최대값을 출력한다.

 

📌CODE

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

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

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def bfs(i, j, k):
    q = deque()
    q.append((i, j))
    visited[i][j] = 1
    while q:
        ci, cj = q.popleft()
        for l in range(4):
            ni = ci + dr[l]
            nj = cj + dc[l]
            if 0<=ni<N and 0<=nj<N and heights[ni][nj]>=k and not visited[ni][nj]:
                visited[ni][nj] = 1
                q.append((ni, nj))

max_height = max(map(max, heights))
min_height = min(map(min, heights))
ans = min_height
for k in range(min_height, max_height+1):
    visited = [[0] * N for _ in range(N)]
    cnt = 0
    for r in range(N):
        for c in range(N):
            if heights[r][c]>=k and not visited[r][c]:
                bfs(r, c, k)
                cnt += 1
    ans = max(ans, cnt)

print(ans)