[알고리즘] DFS

그래프 탐색

• 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

DFS

Depth First Seaarch : 깊이 우선 탐색

• 루트 노드에서 시작해서 하나의 Branch를 먼저 완벽하게 탐색하는 방법
• 시작 정점에서 하나의 분기를 완벽하게 탐색하고, 탐색이 끝나면 다른 분기를 탐색하는 방법
• 사용 예시 : 모든 노드를 방문하고자 할 때 사용함
  
  

DFS와 BFS의 차이

• DFS : 깊이 우선 탐색
• BFS : 너비 우선 탐색

그림을 보면 한눈에 차이점이 보이지 않는가?
DFS는 깊게를 우선으로 탐색하고, BFS 넓게를 우선으로 탐색한다.

그래서 DFS는 재귀로 작성할 수 있겠고, BFS는 그렇지 않다.

• DFS가 BFS보다 좀 더 간단하다
• 단순 검색 속도는 BFS가 더 빠르다
  
  

DFS의 특징

• 어떤 노드를 방문했는지 여부를 반드시 검사해야함.
• 탐색을 하다가, 한 분기를 모두 탐색했으면 부모 노드로 되돌아간다.
  • Stack을 이용하여 탐색이 가능하다.
  • 또한 재귀 함수로도 탐색이 가능하다.
• 백트래킹에서 많이 사용됨.
• BFS는 최단 경로를 보장하지만, DFS는 최단 경로를 보장하지 않음.
  • 그 이유가, 한 분기에서 노드를 찾아내면 그 즉시 종료하기 때문.
  • 다른 최단 경로가 있는지 파악할 수 없음.
    
    

DFS의 과정 (Stack으로 구현)

1. Stack에 갈 수 있는 노드를 삽입함
2. Stack에서 pop 연산하여 그 노드 부터 탐색함.
3. 계속해서 갈 수 있는 노드를 Stack에 삽입
4. 한 분기를 다 탐색하면, pop연산 후 다른 분기를 탐색 할 수 있음

DFS 과정 (BackTracking)

계속해서 Visited를 기록해두어 Stack에 중복으로 삽입되어 이미 방문한 노드는 순회하지 않도록 해야한다.

DFS 코드

from collections import deque

def dfs(graph, start_node):    
    visited = []
    need_visited = deque()
    
    ##시작 노드 설정해주기
    need_visited.append(start_node)
    
    ## 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:
        ## 시작 노드를 지정하고
        node = need_visited.pop()
 
        ##만약 방문한 리스트에 없다면
        if node not in visited:
 
            ## 방문 리스트에 노드를 추가
            visited.append(node)
            ## 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])
                
    return visited

파이썬에서, Stack을 사용하기 위해 deque를 사용하여 pop /append 연산을 사용한다.

인접한 노드들을 아직 방문하지 않았으면, deque에 넣고 visited를 체크하는 모습이다.

need_visited.extend(graph[node]) 코드를 이용하여 갈 수 있는 모든 경로를 삽입하는 모습이다.

DFS의 시간 복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)
• 너비 우선 탐색(BFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
  
  

Reference.

• [필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해
• DFS 완벽 구현하기 [Python]
• [알고리즘] 깊이 우선 탐색(DFS)이란