[파이썬 알고리즘] 쉽게 이해하는 DFS 알고리즘 (정의, 특징, 코드)

0. DFS 정의

• DFS는 Depth-First Searh, 깊이 우선 탐색이라고도 불린다.
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• 코드에서 그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현될 수 있다.
• DFS는 스택자료 구조를 이용한다.

 

 

1. DFS 동작과정

• 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상위 노드를 꺼낸다.
• 3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

간단히 말하면 시작 노드에서부터 시작해서, 인접해 있는 노드를 향해 쭉 나아가면서 더 나아갈 수 없다면

이전 노드로 돌아간다. 이전 노드에서 더 나아갈 수 있으면 가고, 아니면 또 이전 노드로 간다. (이와 같이 반복)

 

그림1. 그래프

다음 그림을 예제로 보자.

순서는 1번에서부터 시작하고, 번호가 낮은 순서부터 우선적으로 처리된다고 가정해보자.

그리고 노드를 방문 시 방문처리를 한다.

• 1번 시작 -> 2번으로 감 -> 4번으로 감 -> 6번으로 감 -> 더 나아갈 수 없음 이전 노드로 복귀
• 4번 나아가기x -> 2번 나아가기x  -> 1번으로 돌아왔는데 3번으로 갈 수 있음
• 3->5으로 간다. -> 5번 더 나아갈 수 없음 -> 3번으로 복귀
• 7번으로 나아갈 수 있음->더 나아갈 수 없음 -> 3번 복귀 -> 1번 복귀 -> 끝
• 탐색 순서 = 1->2->4->6->3->5->7

 

 

2. DFS 코드

아까 그린 그림을 기반으로 코드를 작성해보자.

def dfs(graph, v, visited):
    
    #v는 시작위치
    visited[v] = True
    print(v , end = ' ')
    
    #현재 노드와 연결된 노드를 재귀적으로 호출
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    
graph = [
    [],
    [2,3,7],
    [1,4,6],
    [1,5, 7],
    [2,6],
    [3,7],
    [2,4],
    [1,3]
]

#각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False] * 9

print("방문순서")
dfs(graph, 1, visited)

Output :

방문순서 

1 2 4 6 3 5 7 

 

 

 

3. DFS 특징

• DFS는 각 Level에 일부분만 저장하므로 BFS에 비해 메모리 메모리 사용률이 적다.
• 찾고자하는 답이 트리에서부터 멀어질 수록 DFS가 유리하다. (BFS에 비해)
• 트리 전체를 순회하고자 할 때 유리하다.
• 사용하고자 하는 의도에 따라 전위 순회(Pre-order), 중위 순회(Inorder), 후위 순위(Post-order)로 나뉠 수 있다.
• DFS의 대표적인 순회 방식은 전위 순회(Pre-orfer Traverse)이다. 

 

 

 

 

 

참조

이것이 코딩 테스트다 with 파이썬 / 지은이 나동빈

https://brilliant.org/wiki/depth-first-search-dfs/