[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다.

 

[ Contents ]

 

 

1. DFS(Depth First Search)

깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식

 

 그래프에서 '노드(Node)'는 원으로 표현된 데이터이며, 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 시작 노드를 1번이라고 할 때, DFS는 하나하나 끝까지 탐색합니다.

 [ 1 -> 2 -> 4 -> 5 -> 6 -> 3 ]

(같은 거리 내 인접한 노드는 작은 노드부터 탐색한다고 가정)

 

 

 

2. 스택(Stack)을 이용한 탐색 방식

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

스택(Stack): 후입선출(Last-in-Last-out), 가장 최근에 들어간 자료부터 꺼내는 자료구조

 

 DFS탐색은 스택을 이용해서 구현합니다. 인접한 노드를 스택에 삽입(push)하고, 꺼내서(pop) 탐색합니다.

 

 

 위에서 살펴봤던 예제를 다시 보겠습니다. 시작 노드는 1번이며, 스택에 방문한 노드를 저장합니다. 주황색 테두리는 방문한 노드를 뜻합니다.

 1번 노드와 인접한 노드는 2번과 3번입니다. 작은 숫자부터 방문한다고 가정할 때, 2번 노드를 방문하고 스택에 저장합니다. 2번 노드와 인접한 노드는 4, 5, 6번 노드이며 숫자가 작은 4번 노드를 방문하고 스택에 저장합니다.

 

 

 4번 노드 이후로는 새로운 인접노드가 없습니다. 즉, 4번 노드가 끝이므로 스택에서 4번을 꺼냅니다. (pop)

 그 다음 스택의 최상단(top) 노드는 2번이며, 2번 노드와 인접한 5번 노드를 스택에 저장하고 탐색합니다.

 

 

 마찬가지로 5번 노드가 끝이므로, 스택에서 5번 노드를 제거합니다. 스택의 최상단 노드가 다시 2번이 되고, 방문하지 않은 6번 노드를 탐색합니다.

 

 

 방문하지 않은 인접노드가 없는 6번, 2번 노드가 스택에서 제거되고 1번 노드가 최상단 노드로 남습니다.

 방문하지 않은 3번 노드를 스택에 저장하고 탐색합니다.

 

 

 방문하지 않은 인접노드가 없으므로 3번, 1번이 스택에서 제거되고 모든 탐색을 마칩니다.

 [ 1 -> 2 -> 4 -> 5 -> 6 -> 3 ]

 

 

 

3. DFS 구현

#dfs 탐색(탐색할 그래프, 시작 노드, 방문여부 리스트)
def dfs(graph, node, visited):
    visited[node] = True #시작 노드 방문
    print(node, end=' ')
    # 인접 노드를 재귀적으로 방문
    for i in graph[node]:
        if not visited[i]: #방문하지 않은 노드라면
            dfs(graph, i, visited) #해당 노드를 시작 노드로 dfs

 DFS는 주로 재귀(recursion)를 이용해서 구현합니다. 재귀 역시, 함수를 stack memory에 쌓아두는 방식이기 때문에, 결과적으로는 스택을 이용하게 됩니다.

 visited 리스트로 탐색(방문) 여부를 표시하고, 방문하지 않은 노드를 탐색합니다.

 이 때, dfs를 재귀적으로 호출하며 인접 노드가 없을 때까지 반복합니다.

 

 

graph = [
   [],
    [2, 3],#1번 노드와 연결된 노드
    [1, 4, 5, 6], #2번 노드와 연결된 노드
    [1], #3번 노드
    [2, 5], #4번 노드
    [2, 4], #5번 노드
    [2] #6번 노드
]

visited = [False]*7 #방문여부 리스트
dfs(graph, 1, visited) #시작 노드 1번

 예제 그래프를 입력으로 넣으면, 같은 결과를 확인하실 수 있습니다.