백준(2468,안전 영역)

문제 설명

입력 1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

출력 1

5

입력 2

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

출력 2

6

손풀이

X

풀이

from collections import deque
import sys

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

for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
        MaxNum = max(MaxNum, graph[i][j])

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(a,b,height):
    q = deque()
    q.append([a,b])
    visit[a][b] = 1 # 방문처리

    while q:
        x,y = q.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
        
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > height and visit[nx][ny] == 0: # 현재 높이보다 높고 방문 하지 않은 곳
                    visit[nx][ny] = 1
                    q.append([nx,ny])
ans = 0

for h in range(MaxNum):
    visit = [[0] * n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > h and visit[i][j] == 0: # 현재 높이보다 높고 방문 하지 않은 곳 확인
                bfs(i,j,h)
                cnt += 1

    ans = max(ans, cnt)

print(ans)