[백준/2468/파이썬] 안전 영역

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

• 어떤 지역의 높이 정보가 주어진다.
• 특정 높이 N보다 낮을때, 장마철이 되면 이 지역의 높이정보에 따라 침수여부가 결정된다.
• 안전지역을 찾아야한다.

이 문제도 , 결국, 연결요소를 찾는 문제이다. 하지만, 연결요소를 찾는 과정에서, 시뮬레이션이 살짝 들어가있는 문제이다. DFS/BFS 둘 다 가능한 문제임. 

• max_height를 먼저 계산해줘서, 침수 될 수 있는 최대 높이를 생각해줬음. ( 사실 높이가 1~100까지라, 100으로 해줘도 될거같긴하지만, 2N^2 vs 100N^2이라, max_height를 찾는게 더 이득임.

 

#2<=N<=100
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N= int(input())
board= [list(map(int,input().split())) for _ in range(N)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
def dfs(y,x,height):
    for k in range(4):
        ny=y+dy[k]
        nx=x+dx[k]
        if 0<=ny<N and 0<=nx<N and not v_chk[ny][nx] and board[ny][nx] > height:
            v_chk[ny][nx] = True
            dfs(ny,nx,height)
            
# max_height를 먼저 계산해주었음.
# max_height가 아니더라도, 101 까지 다 돌아주면 되긴할듯?
# 하지만, max_height가 100이면, 100*N^2을 하냐 vs 2N^2을 하냐의 선택이니까, 난 당연히 MAx_height를 
# 생각해주는 방법으로 갔음.
max_height=0
for i in range(N):
    for j in range(N):
        max_height=max(max_height,board[i][j])

ans=0
for h in range(max_height+1):
    v_chk=[[False]*N for _ in range(N)]
    cnt=0
    for i in range(N):
        for j in range(N):
            if board[i][j] > h and not v_chk[i][j]:
                v_chk[i][j] = True
                dfs(i,j,h)
                cnt+=1
    ans = max(ans,cnt)

print(ans)