[DFS] Depth First Search

DFS란
말 그대로 깊은 부분을 우선적으로 탐색하는 기법이다.

이 알고리즘의 핵심은 스택(stack) 자료구조를 사용하는 것이다.

스택 자료구조는 FILO (First-In-Last-Out) 방식을 따른다. 즉 스택에 데이터를 집어넣을 때 순서와

스택에서 데이터를 꺼낼 때 순서가 역방향이라는 것이다. 

DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나

하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다. 따라서 N! 가지 경우의 수를 가진 문제는

DFS로 처리가 불가능할 것이다. DFS 알고리즘 구체적인 동작 과정은 아래과 같다.

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

여기서 “방문처리” 란 탐색한 노드를 재방문하지 않도록 구분하는 것이다.
즉, 스택에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이다.
물론 스택을 사용하지 않아도 구현은 가능하다.

 

파이썬에서 DFS를 구현할 때는 "스택/큐"를 활용할 수도 있고, "재귀함수"를 통해 구현할 수도 있다.

 

(1) 리스트를 활용한 DFS 구현

def dfs(graph, start_node):
    # 기본은 항상 두개의 리스트를 별도로 관리해 주는 것
    need_visited, visited = list(), list()
    
    # 시작 노드를 시정하기
    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

위 코드는 need_visited 에서 추가된 Node들 중에서 가장 끝에 있는 것을 뽑아서 검색하는 방식이다. 

이 부분이 스택을 활용한 방식인 것이다. 다만, list에서 pop을 활용하면 성능면에서 떨어지는 단점이 있다.

 

 

(1) deque를 활용한 DFS 구현

from collections import deque

def dfs2(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

성능 면에서 list( ) 형태보다 deque 형태가 훨씬 좋다.

 

(1) 재귀함수를 활용한 DFS 구현

def dfs_recursive(graph, start, visited = []):
	visited.append(start)
    
    for node in graph[start]:
    	if node not in visited:
        	dfs_recursive(graph, node, visited)
            
    return visited

visited 자료형을 기본 함수 인자로 포함시키고,

방문한 리스트들을 재귀함수를 통해서 계속 visited에 담는 방식이다.

보통 DFS 를 구현할 때 재귀함수를 많이 활용한다.