깊이우선탐색 구현에 대한 고찰

깊이우선탐색은 탐색 알고리즘이고 스택의 원리를 이용해서 구현된다. (너비우선탐색은 큐, 다익스트라는 힙의 방식을 이용한다)

 

대부분의 사람들은 깊이우선탐색을 함수를 이용해서 구현하고는 한다. 실제로 함수가 호출되고 종료되며 작동하는 것은 스택의 원리와 유사하게 작동하지만 왜 실제로 스택을 이용하지 않는 것일까? 파이썬에서는 특히 이 점을 신경써야 한다. 왜냐하면 기본적으로 재귀 제한이 3천밖에 안되므로 만약 깊이우선탐색으로 일자로 4천개의 노드가 이어져 있는 그래프를 탐색한다면 Recursionerror를 반환할 것이다. 그러므로 sys 라이브러리의 setrecursionlimit을 이용해 재귀 제한을 풀어주어야 한다.

 

이러한 번거로움이나 문제점을 발생시키지 않도록 그러면 스택을 이용해서 구현을 해주면 되는 것이 아닌가?

이 글을 쓰는 나조차도 스택으로 직접 코드를 짜보는 것은 처음이였고 구현하면서야 차이를 찾게 되었다.

 

해당 코드는 2644번문제의 코드이다. 아래는 스택을 이용한 구현이다.

 

from sys import stdin
input=stdin.readline

n=int(input())
first,second=map(int,input().split())
m=int(input())

chon=[[] for i in range(n+1)]
vi=[-1]*(n+1)

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

vi[first]=0

stack=[first]

while stack:
    now=stack.pop()
    for nxt in chon[now]:
        if vi[nxt]==-1:
            vi[nxt]=vi[now]+1
            stack.append(nxt)

print(vi[second])

 

그리고 아래는 일반적인 깊이우선탐색, 함수를 이용한 구현이다.

 

from sys import stdin
input=stdin.readline

n=int(input())
first,second=map(int,input().split())
m=int(input())

chon=[[] for i in range(n+1)]
vi=[-1]*(n+1)

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

vi[first]=0

def dfs(x):
    if x==second:
        return
    for nxt in chon[x]:
        if vi[nxt]==-1:
            vi[nxt]=vi[x]+1
            dfs(nxt)

dfs(first)

print(vi[second])

 

차이가 보이는가? 스택은 현재 노드와 연결된 다른 노드들을 스택에 집어넣지만 함수를 통한 구현에서는 그렇지 않다.

 

예를 들어 1번 노드와 2, 3번 노드가 연결되어 있다면 함수를 통한 구현에서는 한 노드로 넘어가고 다른 노드에는 아직 영향을 주지 않는다. 그와 다르게 스택을 통한 구현은 두 노드 모두를 스택에 집어넣게 된다.

 

실제로 해당 문제는 입력이 작아서 더 그럴 수 있지만 실제 걸린 시간은 비슷했고 만약 입력이 커진다면 한 노드에 연결된 모든 노드를 스택에 집어넣는 스택을 통한 구현이 적어도 메모리는 더 소비할 것이고 또한 특정 상황(한 지점만 찾으면 끝나는 문제와 같이)에서는 필요 없는 노드들도 더 들어가니 더 느릴 것이 분명했고 상황에 따라 더 빨라질 일도 찾지 못하였다.

 

그러므로 결론적으로 적어도 내 구현이 틀리지 않았다면 스택을 통한 깊이우선탐색을 구현할 필요가 없다는 이야기이다.

 

왜 스택을 이용한 깊이우선탐색을 이용하지 않는지 알 수 있는 좋은 기회였다.