[Python] 안전 영역 - 백준 (DFS)

해당 글은 백준 2468번 문제 '안전 영역'을 다룬다.

문제

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

2468번: 안전 영역

 

설명

해당 문제는 BFS/DFS로 풀 수 있는 문제로, 해당 글은 DFS 풀이로 해결하였다.

지역들의 높이 정보를 입력 받을 때, 최대 높이 값을 저장해두고 DFS 탐색을 진행할 때 사용한다.

지역의 높이에 따라 해당 높이 이상이라면 2차원 배열의 행과 열을 모두 DFS로 탐색해준다.

그리고 물에 잠기지 않는 안전한 영역의 최대값을 구하는 것이므로 result를 항상 max 값으로 유지해준다.

또한, 재귀한계를 설정하지 않으면 런타임에러가 뜨므로, 재귀한계를 100000으로 설정해줘야한다.

 

코드

import sys
sys.setrecursionlimit(100000)

n = int(input())
max_value = 0
graph = []
for i in range(n):
    input_list = list(map(int, input().split()))
    max_value = max(max_value, max(input_list))
    graph.append(input_list)

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

def dfs(x, y, h, visited):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < n:
            if visited[nx][ny] == 0 and graph[nx][ny] > h:
                dfs(nx, ny, h, visited)

result = 0
for i in range(max_value):
    visited = [[0]*n for _ in range(n)]
    count = 0
    for r in range(n):
        for c in range(n):
            if visited[r][c] == 0 and graph[r][c] > i:
                dfs(r, c, i, visited)
                count += 1
    result = max(result, count)
print(result)