@[파이썬] [DFS] 백준 2468 안전 영역

문제

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

2468번: 안전 영역

코드

import sys

sys.setrecursionlimit(100000)

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

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


def dfs(r, c):
    visited[r][c] = 1
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if array[nx][ny] == 1 and visited[nx][ny] == 0:
                dfs(nx, ny)


max_h = 0
for i in range(n):
    max_h = max(max_h, max(graph[i]))

result = 0
for i in range(0, max_h):
    count = 0
    visited = [[0] * n for _ in range(n)]
    array = [[0] * n for _ in range(n)]
    for j in range(n):
        for k in range(n):
            if graph[j][k] > i:
                array[j][k] = 1
    for j in range(n):
        for k in range(n):
            if array[j][k] == 1 and visited[j][k] == 0:
                dfs(j, k)
                count += 1
    result = max(result, count)

print(result)