2468 - 안전영역 [DFS]

출처 : 백준 2468 안전영역

문제

N*N의 2D 배열이 주어진다. 강수량이 어느 수준일 때 물로 덮히지 않는 영역이 최대로 많은지 알아내는 문제이다. 이 때, 영역이라 함은 상하좌우로 연결되고 강수량 수치보다 값이 높은 숫자들을 의미한다.

처음에는 주어진 배열에서 가장 큰 값을 찾고 for loop을 그 수 만큼 진행을 한다. 그런 다음에 2D 배열을 차례대로 순회하면서 강수량 수치가 현재 진행중인 for loop의 i 보다 크고 아직 방문하지 않은 영역이 있으면 그 영역을 시작으로 DFS를 진행한다. 한번 DFS가 진행되면 해당 수가 들어 있는 영역은 다 방문할 것이고 다음 영역을 찾으러 다시 2D 배열을 순회하게 된다. 이 영역을 찾으면 영역의 수에 1을 더해준다. 2D 배열을 끝까지 순회를 하고 나면 현 영역의 수와 이전 강수량 수치가 더 낮았던 경우에 영역의 수와 비교를 하고 최대값을 취한다.

이 문제를 파이썬에서 풀기 위해서 무조건 sys.setrecursionlimit()을 추가해줘야 한다. 이 코드를 삽입하지 않으면 런타임 에러가 발생한다. 공식 도큐먼트에 의하면 해당 코드는 파이썬 인터프리터 stack에 최대 깊이를 지정하는 것이다. 무한대의 recursion이 발생해서 overflow가 발생하는 것을 방지하기 위함이다. 이 문제에서는 그 만큼 깊이 있게 recursion으로 stack이 쌓이기 때문에 어느 정도가 진행되면 제한을 둬야 하는 것이다.

풀이

# BOJ 2468 - 안전 영역
import sys
sys.setrecursionlimit(100000)
r = sys.stdin.readline

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def dfs(x, y, h):

    for m in range(4):
        nx = x + dx[m]
        ny = y + dy[m]

        if (0 <= nx < N) and (0 <= ny < N) and not visit[nx][ny] and zone[nx][ny] > h:
            visit[nx][ny] = True
            dfs(nx, ny, h)


N = int(r())
zone = [list(map(int, r().split())) for _ in range(N)]

ans = 1
for k in range(max(map(max, zone))):
    visit = [[False]*N for _ in range(N)]
    safe = 0
    for i in range(N):
        for j in range(N):
            if zone[i][j] > k and not visit[i][j]:
                safe += 1
                visit[i][j] = True
                dfs(i, j, k)
    ans = max(ans, safe)

print(ans)