2468번 파이썬

처음에 visited를 append로 추가하는 식으로 방문한 것을 관리했더니 시간소요가 컸다. 다른 사람들을 보니까 visited를 0값을 1로 바꿔주는 방법을 쓰길래 나도 사용해봤더니 시간 초과 에러는 뜨지 않았다!!

이 문제는 간단하게 bfs를 이용해서 풀 수 있다.

높이의 최솟값부터 최댓값까지 잠기는 높이를 for문으로 돌려주면 되고 모든 idx를 검사해서

h보다 크고 방문하지 않는 지점이 있다면 bfs문을 돌려서 그 지점의 최대 영역을 방문 지점에 넣고 cnt를 1증가 시켜준다.

새로운 높이마다 최대 영역이 되는 구간이 달라지기 때문에 visited를 항상 초기화해주어야 하고 

(# visited=[[0]*n]*n 이렇게 작성할 경우 [0]*n이 n번 복사되는 것이므로 한 행의 값이 바뀌면 모든 행의 값이 바뀌므로 아래처럼 작성해줘야한다!!)

높이의 최솟값에서 -1 한 값부터 for문을 돌리는 이유는

모두 물에 잠기지 않는 최대 영역이 경우가 답이 될 수 있기 때문이다(잠기는 높이가 최솟값보다 작을 경우 최대영역은 모든 영역이고 res가 1인 경우다)

import sys
input = sys.stdin.readline
n = int(input())
ary = [list(map(int,input().split())) for i in range(n)]
from collections import deque
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(row,col,h,visited):
  queue = deque([[row,col]])
  visited[row][col]=1
  while queue:
    item = queue.popleft()
    for i in range(4):
      n_row=item[0]+dx[i]
      n_col=item[1]+dy[i]
      if 0<=n_row<n and 0<=n_col<n and ary[n_row][n_col] > h and not visited[n_row][n_col]:
        queue.append([n_row,n_col])
        visited[n_row][n_col]=1

maxm= max(max(ary))
minm= min(min(ary))
res=-1
for h in range(minm-1,maxm):
  visited = [[0]*n for _ in range(n)]
  cnt = 0
  for r in range(n):
    for c in range(n):
      if ary[r][c] > h and not visited[r][c]:
        bfs(r, c, h,visited)
        cnt += 1
  if cnt > res:
    res = cnt
print(res)