DFS를 구현할 때, 스택을 사용하는 방법과 재귀함수를 사용하는 방법의 두 가지 방법이 있습니다. 저는 지금까지 항상 재귀함수를 사용해 구현했는데, BOJ에서 DFS문제를 푼 다른 분들의 코드를 보면 스택을 사용해 구현하시기도 하더라구요! 그래서 공부 겸 스택을 사용한 DFS에 대해서도 알아보려 합니다. 본 포스팅은 DFS, 스택, 재귀함수의 개념에 대한 설명은 하지 않으므로 이를 모르신다면 미리 알고 오시길 추천드립니다!
위의 그래프를 DFS로 탐색해보겠습니다. 이 그래프를 2차원 리스트로 표현하면 아래와 같습니다.
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]`graph[n]`은 노드 n에 연결된 노드들의 리스트를 뜻합니다. 예를 들어 `graph[3] = [1, 4, 5]`라는 것은 3번 노드는 1번, 4번, 5번 노드와 연결되어 있음을 의미합니다.
DFS 함수를 각각 재귀함수와 스택으로 정의해서 위 그래프를 한번 넣어보도록 하겠습니다.
1. 재귀함수를 사용한 DFS 구현
아마 일반적으로 스택보다 더 많이 사용되고 있는 듯 합니다. 나동빈 님의 유명한 책인 <이것이 취업을 위한 코딩 테스트다 with 파이썬>의 DFS 파트에서도 재귀함수로 구현하는 법이 나와있습니다. 저도 이 책으로 DFS를 처음 공부했기 때문에 재귀함수로 구현하는 법을 먼저 익혔습니다.
코드
# DFS 함수 정의
def dfs(v):
# 현재 노드를 방문 처리
visited[v] = 1
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if visited[i] == 0:
dfs(i)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [0] * 9
# 정의된 DFS 함수 호출
dfs(1)실행 결과
1 2 7 6 8 3 4 5재귀함수로 DFS를 구현하는 기본 아이디어는 재귀함수가 가지는 '스택 메모리'의 특성을 활용하는 것입니다. 함수가 호출되면 운영체제가 스택 메모리에 함수가 사용할 메모리 공간을 할당해 줍니다. 그 함수 안에서 자기 자신 함수를 호출하면, 새롭게 할당된 메모리 공간이 기존 메모리 공간 위에 쌓이게 됩니다. 마치 스택처럼 말이죠! 이렇게 되면 가장 처음 불린 함수는 안쪽 함수들이 리턴하기 전까지 스택 메모리의 최하단에서 계속 기다리다가, 안쪽 함수들이 모두 리턴하면 다시 수행되게 되는 거죠. 결국 DFS의 핵심 원리가 스택이기 때문에 재귀함수로 구현이 가능한 것이겠네요!
2. 스택을 사용한 DFS 구현
그럼 이번엔 스택을 사용해 DFS를 구현해 보겠습니다. 위의 코드에서 구현한 그래프를 그대로 사용해서 같은 결과가 출력되는지 한번 보도록 하죠!
코드
# DFS 함수 정의
def dfs(v):
dfs_stack = [v]
while dfs_stack:
nv = dfs_stack.pop()
if visited[nv] == 1:
continue
print(nv, end=' ')
visited[nv] = 1
dfs_stack.extend(reversed(graph[nv]))
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [0] * 9
# 정의된 DFS 함수 호출
dfs(1)실행 결과
1 2 7 6 8 3 4 5당연하지만 같은 결과가 출력됩니다. 스택을 썼냐, 재귀를 썼냐만 다를 뿐 원리는 같기 때문이지요!
참고로 `dfs_stack`에 값을 추가할 때 `reversed()` 함수를 쓴 이유는 그냥 작은 숫자 노드를 먼저 방문하기 위해서 입니다. 반드시 숫자가 낮은 노드를 먼저 방문할 필요는 없으므로 `reversed()`하지 않고 바로 `extend()`를 하셔도 실행 결과만 다르게 나올 뿐 문제는 없습니다.
3. 둘 중 무엇으로 DFS를 하는 것이 좋은가?
일반적으로 재귀함수를 이용해 DFS를 구현하시는 분들이 더 많고, 재귀함수를 이용한 방법이 더 간단하고 이해도 더 쉽다는 장점이 있는 것 같습니다. 실제로 코드 길이도 재귀함수를 이용한 코드가 더 짧죠.
둘다 스택 구조를 사용한다는 점은 동일하지만, 재귀함수를 사용하게 되면 개발자가 직접 스택 자료구조를 만들지 않아도 운영체제가 알아서 스택구조를 만들어 준다는 장점이 있습니다. 단 그렇다고 스택을 만드는 작업이 엄청나게 복잡한 것까지는 아니니, 본인의 성향에 따라 선택하시면 될 것 같네요!
