Advanced Algorithm - 깊이 우선 탐색(Depth First Search)

1. 깊이 우선 탐색(DFS)이란?

- 방향과 상관없이 오른쪽 또는 왼쪽 노드를 기준으로, 한 노드의 자식노드를 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가는 방식으로 순회하는 탐색

 

a) DFS 예시

• DFS 동작방식: A - B - D - E - F - C - G - H - I - J

---

2. DFS 알고리즘 동작방식의 이해 

- DFS 알고리즘은 Stack과 Queue를 이용하여 구현할 수 있다.

- need_visit Stack과 visited Queue를 사용하여 구현한다. 

- stack의 특성(LIFO)으로 인해 BFS와는 다르게 need_visit Stack에서 꺼내오는 데이터는 가장 나중에 삽입된 데이터다. 

 

 

 

---

3. DFS 알고리즘 코드구현

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        # pop에 0을 넣으면 가장 앞의 데이터를, 
        # 인자가 없으면 가장 마지막 데이터를 뽑아온다.(데이터는 삭제됨)
        
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
            
    return visited

 

 

[테스트 - 그래프 생성]

 

 

[테스트 결과]

---

4. DFS의 시간복잡도

- BFS와 동일하게 DFS 또한 while문이 시간복잡도를 결정하는 요인이 된다. 

- 그러므로 방문해야 하는 노드의 수(need_visit 큐의 길이)에 따라 달라지는 것이다. 

- 이를 바탕으로 노드의 수를 V(vertex), 간선의 수를 E(edge)로 표시하여 시간 복잡도를 표현한다. 

 

• BFS의 시간복잡도 = O(V+E)