[백준 | python] 안전 영역

• 문제 링크: https://www.acmicpc.net/problem/2468
• BFS/DFS

 

Q1) 문제를 어떻게 이해했나요?
A1) NxN 격자에 각 칸의 높이가 주어진다. 비가 와서 수위 h이하의 칸은 전부 잠긴다. 잠기지 않은 칸들 중 상하좌우로 연결된 덩어리를 "안전 영역"이라고 한다. 비의 수위 h를 모든 가능한 값으로 바꿔가며 안전 영역 개수를 세어보고, 그 중 최대값을 구하는 문제

Q2) 문제를 어떻게 풀 예정인가요?
1. 0부터 최대 수위까지 탐색
2. 각 h에 대해서 모든 칸을 순회하며 영역 개수를 구함
3. 시간 복잡도 O(N^2)

 

고민했던 부분

영역을 어떻게 구하는거지? 사방이 막히는 걸 항상 다 확인하는 코드를 추가해야하나? 비효율적인 것 같은데..

그런데, 영역은 '높이 > h'인 칸들의 연결요소이고, BFS로 한 번에 싹 방문하면 큐가 비는 순간이 그 영역이 경계로 볼 수 있다. 

 

 

💡 정답

from collections import deque

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

max_height = max(max(row) for row in area)
max_safe_zone = 0

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

def bfs(x, y, rain, visited):
    queue = deque([(x, y)])
    visited[x][y] = True

    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < N and 0 <= ny < N:  # 격자 밖이면 못 감(경계에 막힘)
                if not visited[nx][ny] and area[nx][ny] > rain: # 이미 방문한 곳은 다시 안 감(중복 막음), # 잠긴 칸(<=rain)은 못 감(물에 막힘)
                    visited[nx][ny] = True
                    queue.append((nx, ny))

for rain in range(max_height + 1):  # 비의 높이 0부터 최대 높이까지
    visited = [[False]*N for _ in range(N)]
    safe_zone_count = 0

    for i in range(N):
        for j in range(N):
            if not visited[i][j] and area[i][j] > rain:
                bfs(i, j, rain, visited)
                safe_zone_count += 1

    max_safe_zone = max(max_safe_zone, safe_zone_count)

print(max_safe_zone)