오타를 찾느라 고생을 좀 했다...
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))
'[BOJ] - Python' 카테고리의 다른 글
[백준] 9205 : 맥주 마시면서 걸어가기 python (0) | 2023.08.24 |
---|---|
[백준] 14503 : 로봇 청소기 python (0) | 2023.08.24 |
[백준] 1525 : 퍼즐 python (0) | 2023.08.19 |
[백준] 10451 : 순열 사이클 python (0) | 2023.08.19 |
[백준] 11724 : 연결 요소의 개수 python (0) | 2023.08.18 |