[백준] 2468 - 안전 영역 [Python(파이썬)]

문제

www.acmicpc.net/problem/2468

2468번: 안전 영역

풀이

입력부에서 가장 높은 지역의 높이(MAX)를 저장한다. 그 후 강수량을 1부터 MAX-1까지 정해서 DFS를 진행한다.

이때, 강수량보다 높은 지역에 한해서만 탐색을 진행하고, 탐색이 끝나면 비교를 통해 안전 영역의 최댓값을 구한다(비가 안 오는 경우도 존재하므로 최댓값은 1이상이다).

 

코드

import sys
sys.setrecursionlimit(10**9)

def dfs(y, x, r):
    visited[y][x] = 1

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if g[ny][nx] > r and not visited[ny][nx]:
                dfs(ny, nx,r)

dy = [1, 0, -1 , 0]
dx = [0, 1, 0, -1]
g = []
result = 1
MAX = float('-inf')
n = int(sys.stdin.readline().strip())

# input
for _ in range(n):
    _input = [int(x) for x in sys.stdin.readline().split()]
    _max = max(_input)
    if _max > MAX:
        MAX = _max
    g.append(_input)

# DFS
for i in range(1, MAX):
    visited = [[0]*n for _ in range(n)]
    cnt = 0
    for j in range(n):
        for k in range(n):
            if g[j][k] > i and not visited[j][k]:
                dfs(j, k, i)
                cnt += 1
    if cnt > result:
        result = cnt

print(result)