[백준] 2648 안전영역 Python

[백준] 2648 안전영역 Python

이 문제를 처음 풀 때에는 복잡하게 풀었던 것 같다.반복문을 얼마나 반복했는지 모른다.
이 문제는 map의 가장 작은 수 부터, 가장 높은 수-1까지 반복문을 돌려 bfs를 몇번 실행하게 되는지 count를 하여 제일 큰 안전영역의 수를 return 해야한다.
여러 배열을 선언하지 말고, 부등호를 활용했다.
그리고 높이가 9인 경우는 다 잠기게 되어 안전영역은 0이다 따라서 가장 높은 수를 고려할 필요가 없다.
2미만인 경우 안잠기게 된다.

import sys
from collections import deque
sys.stdin=open("input.txt")
n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
small=200
big=-100

for i in graph:
    small=min(small,min(i))
    big=max(big,max(i))

if small==big:
    print(1)
    exit()

#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]


result = []


def bfs(si,sj,small):
    q=deque()
    q.append((si,sj))

    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 graph[nx][ny]>small and not visited[nx][ny]:
                    visited[nx][ny]=True
                    q.append((nx,ny))


for i in range(small,big,1):
    cnt=0
    visited = [[False for _ in range(n)] for _ in range(n)]

    for j in range(n):
        for k in range(n):
            if graph[j][k]>i and not visited[j][k]:
                bfs(j,k,i)
                cnt+=1
    result.append(cnt)

print(max(result))