[백준 24479번] 알고리즘 수업 - 깊이 우선 탐색 1

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

import sys
sys.setrecursionlimit(10**5)
n,m,r=map(int,sys.stdin.readline().split())
visited=[0 for _ in range(n+1)]
graph=[[] for _ in range(n+1)]
cnt=1
def dfs(start):
    global cnt
    visited[start]=cnt
    cnt+=1

    for i in graph[start]:
        if visited[i]==0:
            dfs(i)

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

for i in range(1,n+1):
    graph[i].sort()

dfs(r)

for i in range(1,n+1):
    print(visited[i])

깊이 우선 탐색을 이용하여 푸는 기본 문제이다.

 

다만 메모리 초과와 시간 초과가 지속해서 발생했었는데 이유는 아래와 같았다.

 

1. 시간 초과 : Python3를 사용하면 그 자체로 너무 느려서 시간 초과가 발생한다.

 

2. 메모리 초과 : PyPy3같은 경우 시간 초과는 발생하지 않으나 메모리 초과가 발생하였는데,

setrecursionlimit의 동작 방식이 그만큼의 재귀 깊이를 견딜만큼 충분한 스택 크기를 미리 받아놓는 방식이기 때문이다.

10**5보다 크게 인자를 주면 메모리를 그 자리에서 수십 기가바이트를 할당받으려고 하기 때문에 메모리 초과가 발생한다.

따라서 sys.setrecursionlimit(10**5) 만큼의 재귀만을 허용하면 해결된다.