[자료구조 및 알고리즘] 깊이우선탐색(DFS)
DFS(깊이우선탐색)는 BFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. DFS는 스택으로 구현할 수 있다. 하지만, 스택을 사용하지 않고도 재귀로 충분히 구현이 가능한데 컴퓨터에서 함수 호출의 과정이 스택으로 구현되는 것을 생각해보면 이해가 될 것이다.
DFS, BFS 모두 인접행렬과 인접리스트 두 가지로 구현할 수 있다. 인접행렬로 구현할 경우 특정 item에 접근해 연결성 여부를 검사하는 것은 빠르지만 무조건 O(n^2)만큼의 메모리가 필요하다. 연결리스트를 사용한 인접리스트로 구현하는 경우 메모리 사용을 줄일 수 있지만 특정 item에 접근해 연결성 여부를 검사하는 과정이 좀 느릴 수 있다. 하지만 데이터가 많지 않은 경우 접근에 필요한 시간이 많이 소요되는 것은 아니므로 연결리스트를 사용해 구현하는 것이 좀 더 일반적이다.
아래와 같은 그래프가 있을 때, 이를 DFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 스택에 넣어주는 것이다.
전체적인 알고리즘은 다음과 같다.
- 스택의 최상단 노드를 확인한다
- 최상단 노드와 연결된 아직 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 뺀다.
먼저 1번 노드를 스택에 넣고 방문처리한다.
1번 노드와 연결된 2번 노드를 방문처리하고 스택에 넣어준다.
2번 노드와 연결된 3번 노드를 스택에 넣고 방문처리해준다.
3번 노드와 연결된 6번 노드를 스택에 넣고 방문처리해준다.
6번 노드와 연결된 7번 노드를 스택에 넣고 방문처리해준다.
7번 노드와 연결된 노드가 더 이상 없으니 7번 노드를 스택에서 뺀다. 마찬가지로 6,3번 노드로 뺀다. 그러면 스택의 최상단 노드가 2번이 되는데 2번과 연결된 노드로 4번이 있으니 방문처리하고 스택에 넣어준다.
4번과 연결된 5번을 스택에 넣고 방문처리해준다.
5번과 연결된 미방문 노드가 없으니 스택에서 뺀다. 마찬가지로 4,2,1번 노드를 뺀다.
결과적으로, DFS를 이용하면 방문순서는 1->2->3->6->7->4->5가 된다. 파이썬 코드로 구현하면 다음과 같다.
visit = [False for _ in range(8)]
a = [[] for _ in range(8)]
def dfs(x):
if visit[x]: return
visit[x] = True
print(x)
for y in a[x]:
dfs(y)
# 연결리스트 구현
connection = [(1,2),(1,3),(2,3),(2,4),(2,5),(4,5),(3,6),(3,7),(6,7)]
for i,j in connection:
a[i].append(j)
a[j].append(i)
dfs(1)
참고