백준 2468 안전 영역 (파이썬)

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

2468번: 안전 영역

1. 비가 내린 이후의 지역을 구한다

2. bfs로 안전한 영역의 개수를 구한다

3. 최대값을 구하여 출력

from collections import deque
import copy

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

def bfs(x, y):
    q.append([x, y])
    c[x][y] = 1
    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:
                if m[nx][ny] != 0 and c[nx][ny] == 0:
                    q.append([nx, ny])
                    c[nx][ny] = 1

def rain(rain_height):
    for i in range(n):
        for j in range(n):
            if m[i][j] <= rain_height:
                m[i][j] = 0

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
q = deque()
ans = 0

height = 0
for i in a:
    max_height = max(i)
    height = max(max_height, height)
height -= 1

while height >= 0:
    m = copy.deepcopy(a)
    c = [[0]*n for _ in range(n)]
    cnt = 0

    rain(height)
    for i in range(n):
        for j in range(n):
            if m[i][j] != 0 and c[i][j] == 0:
                bfs(i, j)
                cnt += 1

    ans = max(ans, cnt)
    height -= 1

print(ans)