[백준_2468] 안전영역 python

왤케 dfs가 bfs보다 어려운 느낌인지,,

# n 입력
n = int(input())

# town 입력
town = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n

# check(x, y, h)
def check(x, y, h):
    # 범위 내에 있고, 방문한 적 없고, 현재 높이보다 높으면 통과
    return in_range(x, y) and not visited[x][y] and town[x][y] > h

# dfs(x, y, h)
def dfs(x, y, h):
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        # 다음 위치
        nx, ny = x + dx, y + dy
        # 갈 수 있으면,
        if check(nx, ny, h):
            # 방문처리해주고
            visited[nx][ny] = 1
            # dfs 호출
            dfs(nx, ny, h)

# 설계
# 최대 높이 찾기
import sys
max_height = -sys.maxsize
for i in range(n):
    for j in range(n):
        if town[i][j] > max_height:
            max_height = town[i][j]

# 최대 안전 영역 개수
max_safe_area = 1

# 최대 리커전 횟수 올려주기
sys.setrecursionlimit(100000)

# 높이 1부터 최대높이 전까지 시뮬레이션 하면서
for h in range(1, max_height + 1):
    
    # 안전 영역 갯수
    safe_area = 0

    # visited 설계 및 초기화
    visited = [
        [0] * n
        for _ in range(n)
    ]

    # town 돌면서
    for i in range(n):
        for j in range(n):
            # 침수 높이보다 높고, 방문한 적 없으면,
            if town[i][j] > h and not visited[i][j]:
                # safe_area 하나 올려주고,
                safe_area += 1
                # 방문 처리 해 주고
                visited[i][j] = 1
                # dfs 호출
                dfs(i, j, h)

    # 계산한 안전 영역 갯수가 현재 최댓값보다 크다면
    if safe_area > max_safe_area:
        # 최댓값 갱신
        max_safe_area = safe_area

# 출력
print(max_safe_area)