문제
접근
강수량을 x라고 할 때, board에 x 이하인 칸들은 막혀있다고 생각하면 간단해진다.
그러면 열린 공간들의 개수를 세는 문제인데, 모든 강수량에 대해서 이를 반복해주면 된다.
나는 입력을 받을 때, 최대 높이를 구해두고, 강수량을 1부터 최대 높이까지 반복하며 영역의 개수를 구해주었다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from collections import deque
n = int(input())
dx = [0,0,-1,1]
dy = [-1,1,0,0]
board = []
maxRain = 0
for i in range(n):
tmp = [int(i) for i in input().split()]
m = max(tmp)
if maxRain < m:
maxRain = m
board.append(tmp)
def findRect(rain, i, j):
q = deque()
q.append((i,j))
while q:
tx, ty = q.popleft()
for x, y in zip(dx, dy):
nx = x + tx
ny = y + ty
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] > rain and visit[nx][ny] == 0:
q.append((nx,ny))
visit[nx][ny] = 1
ans = 1
for rain in range(maxRain):
visit = [[0 for _ in range(n)] for _ in range(n)]
zone = 0
for i in range(n):
for j in range(n):
if visit[i][j] == 0 and board[i][j] > rain:
zone += 1
visit[i][j] = 1
findRect(rain, i, j)
if ans < zone:
ans = zone
print(ans)