[백준] 2468 : 안전 영역 python

 

오타를 찾느라 고생을 좀 했다...

 

 

import sys
from collections import deque
input = sys.stdin.readline
 
n = int(input())
graph = []
 
for i in range(n):
    graph.append(list(map(int,input().split())))
 
# 최대 높이를 변수에 저장
max_height = max(map(max,graph))
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
def bfs(graph,visited,x,y,h):
    queue = deque()
    queue.append((x,y))
    visited[x][y] = True
 
    while queue:
        a,b = queue.popleft()
 
        for i in range(4):
            nx = a+dx[i]
            ny = b+dy[i]
 
            if nx>=0 and nx<n and ny>=0 and ny<n:
            # 아직 방문하지 않은 인접한 칸이 안전한 곳이라면 큐에 넣음
                if not visited[nx][ny] and graph[nx][ny]>h:
                    queue.append((nx,ny))
                    visited[nx][ny]=True
 
# 각 경우의 안전한 영역 개수를 저장하기 위한 리스트
res = []
 
# 0부터 최대 높이-1까지 반복
for i in range(max_height):
	# 안전한 영역 개수 초기화
    cnt = 0
    # 방문 체크용 리스트 초기화
    visited = [[False for j in range(n)]for k in range(n)]
    for j in range(n):
        for k in range(n):
        	# 아직 방문하지 않았고 안전한 곳이라면 그 지점에서 BFS 수행
            if graph[j][k]>i and visited[j][k]==False:
                bfs(graph,visited,j,k,i)
                cnt+=1
	# 각 경우의 안전 영역 개수를 res에 추가함
    res.append(cnt)
# 안전 영역의 개수 중 최대인 것을 출력함
print(max(res))