[백준] 2573번 빙산 - 파이썬/DFS

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

import sys
sys.setrecursionlimit(10**6)
from collections import deque

N,M = map(int,input().split())

graph = []

for i in range(N):

    elem = list(map(int,input().split()))

    graph.append(elem)

# 1년 후 빙산을 구하는 함수
def year(graph):

    array = deque([]) # 빙산과 맞닿은 바다의 갯수를 구함

    for i in range(1,N-1):
        for j in range(1,M-1):
            if graph[i][j] !=0:
                check_list = [  graph[i-1][j],graph[i+1][j],graph[i][j-1],graph[i][j+1]]
                array.append(check_list.count(0))

# 맞닿은 면의 갯수만큼 빙산의 높이를 줄여줌
    for i in range(1,N-1):
        for j in range(1,M-1):
            if graph[i][j] !=0:
                arround = array.popleft()
                graph[i][j]-=arround
                if graph[i][j]<0:
                    graph[i][j] = 0

    return graph


def dfs(x,y,visited,graph):

    visited[x][y]=True
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    for i in range(4):

        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<N and 0<=ny<M and graph[nx][ny]!=0:
            if not visited[nx][ny]:
                dfs(nx,ny,visited,graph)

t = 0 # 년차
while True:
    print(graph)
    result = 0
    visited = [ [False] * M for _ in range(N) ]
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and graph[i][j] != 0:
                dfs(i,j,visited,graph)
                result+=1

    if result > 1:
        print(t)
        break

    else:
        t += 1
        graph = year(graph)

		# 빙산이 한번에 녹을때 경계조건
        if sum(map(sum,graph))==0:
            print(0)
            break

난이도는 그렇게 어렵지 않다.

그런데 파이썬에서 DFS로 풀면 메모리 초과 혹은 시간 초과를 보기 정말 쉽다. (백준 정답비율이 낮은 이유)

pypy3으로 제출하고 재귀제한은 10**4 로 해야 통과한다.