[Python/파이썬 백준 2468] 안전 영역(BFS)

www.acmicpc.net/problem/2468

2468번: 안전 영역

풀이

check 해주는 그래프를 3중 리스트로 사용했는데 z 범위를 가장 큰 높이로 받아서 3중 리스트를 선언해주었습니다.

z를 0~height-1 까지 범위를 잡아서 BFS를 돌렸는데 z범위가 엄청 헷갈렸...(0을 포함 안하고 돌렸었는데 틀렸다해서 넣었더니 성공... 안내릴 경우도 포함해주는건가...)

cnt로 안전 영역을 세주고

최대 영역 값을 max로 판단했더니 성공~

#안전 영역
# z를 0~ 제일 큰 높이까지 계산해줘서
# check를 3중 그래프로 만들어주는데 z를 높이를 나타내는데 사용
from collections import deque
import sys
input=sys.stdin.readline

graph=[]
n=int(input())

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

for _ in range(n):
    h=list(map(int,input().split()))
    for i in range(len(h)):
        height = max(h[i],height)
    graph.append(h)

check=[[[False]*n for _ in range(n)]for _ in range(height)]
def bfs(x,y,z):
    queue=deque()
    queue.append([x,y])
    check[z][x][y]=True
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n and check[z][nx][ny]==False and graph[nx][ny]>z:
                queue.append([nx,ny])
                check[z][nx][ny]=True

for z in range(0,height):
    cnt=0
    for i in range(n):
        for j in range(n):
            if graph[i][j]>z and check[z][i][j]==False:
                bfs(i,j,z)
                cnt+=1
        max_size=max(max_size,cnt)

print(max_size)