[백준/Python] 2468. 안전 영역

 

 

 

 

 

• BFS를 이용하여 풀었다.

import copy
from collections import deque

N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
acc = copy.deepcopy(arr)
directy = [-1,1,0,0]
directx = [0,0,-1,1]
result = []

def bfs(y,x): # 인접해있는 지역을 모두 False로 바꿈
    q = deque([(y,x)])
    arr[y][x] = False

    while q:
        y,x = q.popleft()

        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= N or dx < 0: # 배열을 벗어난다면 continue
                continue
            if arr[dy][dx] != False: # 목표좌표가 False이 아니라면 False로 바꿔줌
                arr[dy][dx] = False
                q.append([dy,dx])


for l in range(101): # 높이가 최대 100이므로 100까지 증가하는 for 문
    arr = copy.deepcopy(acc) # for문을 돌 때마다 arr배열과 cnt(안전영역) 초기화
    cnt = 0

    for j in range(N):
        for i in range(N):
            if arr[j][i] <= l: # 비의 양보다 낮으면 해당 좌표를 False로 만들어줌
                arr[j][i] = False

    for j in range(N):
        for i in range(N):
            if arr[j][i] != False: # False이 아니라면 bfs 함수 호출하고 cnt += 1
                bfs(j,i) 
                cnt += 1

    result.append(cnt) # 안전영역을 result에 추가

    if cnt == 0: # 모든지역이 물에 잠긴다면 그 이후는 의미 없으므로 break
        break

print(max(result))