[백준 2468번] 안전 영역 - Python

문제

2468번: 안전 영역

 

---

풀이

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

N = int(input())

max_rain = 0

graph = []
for _ in range(N):
    row = list(map(int, input().split()))
    graph.append(row)
    max_row = max(row)
    max_rain = max(max_rain, max_row)

now_rain = 1

max_safe_area = 0

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

cnt_list = []

def bfs(i, j, k):
    queue = deque()
    queue.append([i, j])
    visited[i][j] = 1

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

            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == 0:
                    if graph[nx][ny] > k:
                        visited[nx][ny] = 1
                        queue.append([nx, ny])

for rain_height in range(max_rain+1):
    visited = [[0 for _ in range(N)] for _ in range(N)]
    safe_area_cnt = 0

    for i in range(N):
        for j in range(N):
            if graph[i][j] > rain_height and visited[i][j] == 0:
                bfs(i, j, rain_height)
                safe_area_cnt += 1

    max_safe_area = max(max_safe_area, safe_area_cnt)

print(max_safe_area)

아이디어

• 물이 잠기지 않는 안전한 영역 -> 현재 비의 양 보다 큰 곳들의 영역 개수를 세주면 됨. 이 부분을 떠올리지 못해 힌트를 얻고 풀었다.
• graph를 BFS로 방문하지 않았고 rain_height보다 큰 지점들을 탐색해 안전 영역을 식별, 개수를 세준다.
• bfs를 호출 전 방문 체크도 하고, bfs 내부에서 queue를 돌 때도 방문 체크를 해줘야 한다.

 

• graph에서 최대 비의 높이를 구한 다음, 1에서부터 시작해 최대 비의 높이까지 각각의 비의 높이에 대해 전체 지도를 순회한다.
• 현재 비의 높이보다 높은 지점에서 bfs를 시작해 연결된 모든 물에 잠기지 않는 지점을 방문 처리한다. 이때마다 safe_area_cnt를 1씩 증가시켜, 해당 비의 높이에서의 안전 영역 개수를 계산한다.
• 모든 비의 높이에 대해 안전 영역 개수를 계산. 가장 높은 값 max_safe_area를 알아낸다.

 

시간 복잡도

BFS의 시간 복잡도는 O(V_정점 + E_간선).
정점은 그래프가 N x N이므로 V = N**2, 간선은 각 노드가 4개의 이웃을 가지므로 E = 4N x N
전체 시간 복잡도 O(max_rain x N**2 x N**2) -> O(N**4)

공간 복잡도

정사각형의 N * N의 graph, visited, bfs 내부 큐 최악의 경우 모든 노드 포함 역시 N * N이므로 O(N**2)