[백준] 2468 안전 영역(Python)

백준 - 2468 안전 영역

풀이

1. bfs와 연결 성분의 개수 구하기

2. bfs의 기준: graph[x][y]의 값이 high(비의 양)보다 높은 경우
   -> 같은 곳을 중복 방문하지 않기 위해 graph[x][y] = high 저장 (visited 사용 x)

3. bfs를 반복하며 연결 성분의 개수 구함 -> 모두 잠기지 않는 경우 ~ 모두 잠기는 경우 반복
   -> 모두 잠기지 않는 경우 : high = 0
   -> 모두 잠기는 경우 : high = 가장 높은 건물의 높이
   ❗️graph의 값을 직접 바꾸기 때문에 다음 반복문에 영향이 가지 않도록 해야함
   -> high = 0부터 시작하면 bfs에서 그래프의 값이 모두 0이 됨

   def bfs(x, y, high):
     ...
     if 0 <= nx < n and 0 <= ny < n and high < graph[nx][ny]:
       graph[nx][ny] = high
      ...

   -> 다음 반복문에 영향
   -> high = max_high(가장 높은 건물의 높이)부터 시작하면 다음 반복문에 영향을 끼치지 않음

4. answer에 연결 성분의 개수가 가장 많은 경우의 개수를 저장

코드

from sys import stdin
from collections import deque

n = int(stdin.readline())
graph = []
answer = 0
max_high = 0

for i in range(n):
    graph.append(list(map(int, stdin.readline().split())))
    max_high = max(max_high, max(graph[i]))

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

def bfs(x, y, high):
    q = deque([(x, y)])
    graph[x][y] = high
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and high < graph[nx][ny]:
                graph[nx][ny] = high
                q.append((nx, ny))

for high in reversed(range(max_high)):
    count = 0
    for i in range(n):
        for j in range(n):
            if high < graph[i][j]:
                bfs(i, j, high)
                count += 1
    answer = max(answer, count)
print(answer)