728x90
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
| 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 |
"""
어떤 지역의 높이 정보를 파악, 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역 최대 몇 개인지 조사
비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠김
안전영역 : 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역
높이가 4 이하인 모든 지점이 물에 잠김
내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5
높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에잠기지 않는 안전한 영역은 네 개
과 열의 개수를 나타내는 수 N
둘째 줄부터 N 개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보
높이는 1이상 100 이하의 정수
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
"""
import sys
from collections import deque
input=sys.stdin.readline
# 네 방향 탐색을 위한 상수 → ↓ ← ↑
dr=[0,1,0,-1]
dc=[1,0,-1,0]
n=int(input())
graph=[list(map(int, input().split())) for _ in range(n)]
# print(graph)
def BFS(i,j,h):
queue=deque()
queue.append([i,j])
visited[i][j]=True
while queue:
r,c=queue.popleft()
for d in range(4):
nextX= r+dr[d]
nextY= c+dc[d]
if 0<=nextX<n and 0<=nextY<n and not visited[nextX][nextY] and graph[nextX][nextY] > h:
visited[nextX][nextY] = True
queue.append([nextX, nextY])
res=0
# 구분 작업 수행
for h in range(100):
cnt = 0
visited = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if not visited[i][j] and graph[i][j]>h:
cnt+=1
BFS(i,j,h)
res=max(res,cnt)
print(res)
728x90