2468: 안전 영역

import sys
from collections import deque

def bfs(x,y):
    global result
    queue = deque()
    queue.append((x,y))
    visited[x][y]=1
    
    while queue:
        p,q=queue.popleft() #fifo
        dx= [0,1,0,-1]
        dy = [1,0,-1,0]
        
        for i in range(4):  #인접한 블럭 검사
            nx = p + dx[i]
            ny = q + dy[i]
            
            if nx <= -1 or nx >= n or ny <= -1 or ny >=n:
                continue
            if graph[nx][ny] > k and not visited[nx][ny]:
            
                visited[nx][ny]=1
                queue.append((nx,ny))
                
    result +=1        
        
    return True

n= int(sys.stdin.readline())
graph=[]

for i in range(n):
    graph.append(list(map(int,input().split())))

sum=1 #초기값 1
for k in range(1,101):
    result=0    #수위마다 result 초기화
    visited=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not visited[i][j]: 
                bfs(i,j)
    
    sum = max(sum,result)                


print(sum)

dfs, bfs 방식 둘 다 가능하나 상기 코드는 bfs 방식이다. 인접한 블럭을 검사하고 배열에 저장하며 더이상 갈 곳이 없으면 하나의 안전영역으로 판단한다. 이를 반복 수행하며 최대의 안전영역 개수를 찾는 방식이다.

dfs 방식은 배열에 저장하지 않고, 인접한 블럭이 안전영역이면 바로 그 블럭으로 건너가서 다시 인접한 배열은 검사하는 방식이다.