[자료구조 및 알고리즘] 깊이우선탐색(DFS)

 

DFS(깊이우선탐색)는 BFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. DFS는 스택으로 구현할 수 있다. 하지만, 스택을 사용하지 않고도 재귀로 충분히 구현이 가능한데 컴퓨터에서 함수 호출의 과정이 스택으로 구현되는 것을 생각해보면 이해가 될 것이다.

DFS, BFS 모두 인접행렬과 인접리스트 두 가지로 구현할 수 있다. 인접행렬로 구현할 경우 특정 item에 접근해 연결성 여부를 검사하는 것은 빠르지만 무조건 O(n^2)만큼의 메모리가 필요하다. 연결리스트를 사용한 인접리스트로 구현하는 경우 메모리 사용을 줄일 수 있지만 특정 item에 접근해 연결성 여부를 검사하는 과정이 좀 느릴 수 있다. 하지만 데이터가 많지 않은 경우 접근에 필요한 시간이 많이 소요되는 것은 아니므로 연결리스트를 사용해 구현하는 것이 좀 더 일반적이다.

아래와 같은 그래프가 있을 때, 이를 DFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 스택에 넣어주는 것이다.

출처 : 안경잡이 개발자 네이버 블로그

전체적인 알고리즘은 다음과 같다.

1. 스택의 최상단 노드를 확인한다
2. 최상단 노드와 연결된 아직 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 뺀다.

먼저 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)

 

참고

• m.blog.naver.com/ndb796/221230945092