[백준][DFS] 2468. 안전 영역 (파이썬/Python)

<오답>

import sys
input = sys.stdin.readline

def dfs(x,y):
    if x >= n or x < 0 or y >= n or y < 0:
        return False
    if graph[x][y] > n:
        graph[x][y] = 0  
        dfs(x,y-1)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x+1,y)
        return True
    return False

n = int(input())
graph = []
cnt = 0

for i in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            cnt += 1
print(cnt)

#틀렸다고 나온다. 그래서 여러 다른 답들을 살펴보았고, 이 문제의 핵심은 안 잠기는 경우도 있다는 것.

#그리고 가장 높은 부분까지 전부 돌아서 안전 영역의 최대부분을 찾아내는 것이다.  

 

<정답>

import sys
from copy import deepcopy
sys.setrecursionlimit(10000)

def dfs(y, x):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if (0 <= y < N) and (0 <= x < N) and t[y][x] > k:
        t[y][x] = k
        for dy, dx in d:
            Y, X = y+dy, x+dx
            dfs(Y, X)        

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max_cnt = 1
for k in range(1, max(map(max, graph))+1):
    t = deepcopy(graph)
    cnt = 0
    for i in range(N):
        for j in range(N):
            if t[i][j] > k:
                dfs(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)

# 초기엔 일반 DFS 문제인 줄 알고 연결된 땅의 크기만 출력하면 되는 줄 알았다.

# 그러나 가장 높은 지역까지 잠기고, 전부 잠기지 않고 할 때 안전지역의 최대값을 구하는 문제였기에 많이 틀리고 여러 답을 보고 생각하며 풀었다