99클럽 코테 스터디 4일차 TIL: 깊이 우선 탐색의 재귀 깊이

오늘의 문제 | 24479. 알고리즘 수업 - 깊이 우선 탐색 1

아주 기초적인 DFS에 대한 내용이겠거니 했다. 물론 내가 그래프 관련 코드를 매우 오랜만에 짜는 것이기 때문에 수도코드를 보고 따라치는 수준이었지만, 그래도 예전에 짠 기억이 있었기 때문에 크게 무리 있지는 않았다.

# 오답 코드 (Recursion Error)
n,m,r=map(int,input().split())
node=[i for i in range(n+1)]
graph=[[] for i in range(n+1)]
visit=[0 for i in range(n+1)]
idx=1

def dfs(node, graph, start):
    global idx
    visit[start]=idx
    idx+=1
    graph[start].sort()
    for end in graph[start]:
        if visit[end]==0:
            dfs(node, graph, end)

for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(node, graph, 1)
print(*visit[1:], sep='\\n')

왜인지는 모르겠지만 오류가 났다. 숫자가 커서 재귀를 돌다가 한계를 초과해버린 듯하다. 재귀 숫자를 늘리는 방법이 있었기에 찾아보기로 했다.

재귀의 깊이: sys.setrecursionlimit()

import sys
sys.setrecursionlimit(1_000_000)

백준 서버에선 기본적으로 재귀의 깊이를 1,000으로 두었다고 한다. 따라서 이 깊이를 1,000,000 정도로 늘려버리면 문제없이 작동할 듯하다.

하지만 이번에는 메모리 초과가 떴다. 아무래도 배열을 너무 많이 사용한 듯하다. 코드를 읽어본 결과 node 배열을 사용할 이유가 없었기에 없애고, 입력값 개수도 많기 때문에 sys.stdin.readline도 사용해보려 한다.

이럼에도 메모리 초과가 떴다. 배열이 많이 커질 경우 사이즈가 꽤나 커지기 때문에 그런게 아닐까 싶었다. 찾아보니 recursionlimit을 10만으로 줄이면 해결이 된다고 한다.

# 정답 코드
import sys
sys.setrecursionlimit(100_000)
input=sys.stdin.readline

n,m,r=map(int,input().split())
graph=[[] for i in range(n+1)]
visit=[0 for i in range(n+1)]
idx=1

def dfs(graph, start):
    global idx
    visit[start]=idx
    idx+=1
    graph[start].sort()
    for end in graph[start]:
        if visit[end]==0:
            dfs(graph, end)

for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(graph, r)
print(*visit[1:], sep='\\n')

오늘의 회고

코드에서는 사소한 오타가 있긴 했지만 그거 말고는 재귀 횟수로 인해 계속 메모리 초과가 났다는게 약간 아쉽다. 파이썬의 문제인가 싶기도 하다. 메모리 초과가 재귀 깊이로 생길 수 있다는 것도 알아둘 필요가 있다는 걸 깨달았다. 너무 크게 잡지 말자.