[BOJ / 백준] 2468 안전 영역 python / 파이썬 dfs

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

2468번: 안전 영역

---

1) 요구사항 분석 : 문제 읽기

안전한 영역의 최대 개수

 

2) 설계 : 접근 방식

높이보다 낮거나 같으면 침수표시해주고(false), 배열 순회 완료했으면 dfs 이용 갯수 세어준다.

처음에 비가 안 오는 경우를 고려하지 않고 높이가 1부터 시작해서 틀렸다..!

import sys
sys.setrecursionlimit(10**6)

이거로 재귀 범위 늘려줌

# BOJ2468 안전 영역
import sys
sys.setrecursionlimit(10**6)

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

# 델타탐색
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def in_range(x, y): # 인덱스 범위 안에 있는지
    return 0 <= x < n and 0 <= y < n

def dfs(i, j):
    global visited
    for x in range(4):
        ni = i + di[x]
        nj = j + dj[x]
        if in_range(ni, nj) and visited[ni][nj]:
            visited[ni][nj] = False
            dfs(ni, nj)

max_area = 0 # 안전 영역의 최대 개수

for h in range(101):
    for i in range(n):
        for j in range(n):
            if arr[i][j] <= h:
                visited[i][j] = False
                
    cnt = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j]:
                cnt += 1
                visited[i][j] = False
                dfs(i, j)
    

    if cnt == 0: # 모든 영역이 물에 잠김
        break
    max_area = max(max_area, cnt)
    visited = [[True for _ in range(n)] for _ in range(n)]


print(max_area)