[Python] 백준 2468번 '안전 영역' 풀이

전형적인 dfs 문제이다.

고려사항

1. 물의 높이의 최소/최대가 정해져있지 않다. 즉, 땅이 물에 안젖는 경우(high=0) 부터 무조건 젖는 경우(high=100)까지 고려해야한다. (잘못봐서 1<=high<=100인줄 알았다가 오류나서 헤맸다.)
2. Recursion Error를 방지하려면 import sys sys.setrecursionlimit(10**7)를 해야한다.

정답

import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline
n = int(input())
maps = [list(map(int, input().split())) for _ in range(n)]

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

max_count = 0

def dfs(y, x, chk, high):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= ny < n and 0 <= nx < n and maps[ny][nx] > high and not chk[ny][nx]:
            chk[ny][nx] = True
            dfs(ny, nx, chk, high)


for high in range(101):
    chk = [[False]*n for _ in range(n)]
    count = 0
    for y in range(n):
        for x in range(n):
            if maps[y][x] > high and not chk[y][x]:
                chk[y][x] = True
                count += 1
                dfs(y, x, chk, high)
    if count == 0:
        break                
    max_count = max(max_count, count)
    

print(max_count)