백준 2468번: 안전영역 (파이썬, DFS)

문제 자체는 기본적인 DFS의 구현이였으나 안전한 영역의 최대 개수를 구하기 위해 한번의 과정이 더 필요하였다.

2차원 배열이기 때문에 각 배열의 원소들에 접근하기 위해서는 2중 반복문이 필수이다.

이때 높이는 1이상 100이하 정수이고 N은 100보다 작으므로 3중 반복문이라 하더라도 100^3=10^6, 시간복잡도는 O(N^3)으로 시간초과에 걸리지는 않는다. 따라서 입력되는 배열들 각각에 max함수를 적용후, 그 값들에 다시 max함수를 적용하여 반복문의 최대 range를 정하고 dfs를 적용하면 된다.

import sys
sys.setrecursionlimit(1000000)

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


def dfs(x, y):
    visited[x][y] = True
    for __ in range(4):
        nx = x + dx[__]
        ny = y + dy[__]
        if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] > min_ and not visited[nx][ny]:
            dfs(nx, ny)


N = int(sys.stdin.readline())

ans = []
graph = []

input_ = list(map(int, sys.stdin.readline().split()))
graph.append(input_)
min_list = set(input_)

for _ in range(N-1):
    input_ = list(map(int, sys.stdin.readline().split()))
    graph.append(input_)
    min_list.update(input_)

visited = [[False]*N for i in range(N)]

for min_ in range(max(map(max, graph))):
    print(min_)
    land_num = 0
    for alpha in range(N):
        for beta in range(N):
            if graph[alpha][beta] > min_ and not visited[alpha][beta]:
                land_num += 1
                dfs(alpha, beta)
    visited = [[False] * N for i in range(N)]
    ans.append(land_num)

land_num = max(ans)
print(land_num)