[그래프] 깊이 우선 탐색 (DFS)

DFS 소개

그래프는 노드와 간선을 이용한 비선형 데이터 구조입니다. 깊이 우선 탐색(Depth First Search)는 시작 노드부터 탐색을 시작하여, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문하는 알고리즘 입니다. 최대 깊이 노드까지 방문한 이후, 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문합니다. 

 

DFS 알고리즘은 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색한다는 특징이 있어, 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있습니다.

 

알고리즘 동작 방식

깊이 우선 탐색은 재귀를 활용한 시스템 스택을 통해 쉽게 구현할 수 있습니다. 

 

탐색을 하려면 일단 시작 노드를 정하고, 스택에 시작 노드를 푸시합니다. 스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드로, 시작 노드를 푸시했다면 아래 과정을 반복합니다.

 

• 스택이 비었는지 확인합니다. 스택이 비었다면, 방문할 수 있는 모든 노드를 방문했음을 의미하므로, 탐색을 종료합니다.
• 스택에서 노드를 팝합니다. 팝한 원소는 최근에 스택에 푸시한 노드입니다.
• 팝한 노드의 방문 여부를 확인합니다. 아직 방문하지 않았다면, 방문 처리합니다.
• 방문한 노드와 인접한 노드를 모두 확인하여, 그 중에서 아직 방문하지 않은 노드를 스택에 푸시합니다.

 

깊이 우선 탐색의 핵심은 '가장 깊은 노드까지 방문한 후에 더 방문할 노드가 없으면 최근 방문한 노드로 돌아와, 해당 노드에서 방문할 노드가 있는지 확인한다' 입니다.

 

DFS 구현

  

    
    
    
    
  
def dfs(current_node):
    # 현재 노드 방문
    visited[current_node] = True
    print(current_node)

    # 인접한 노드 탐색
    for adj_node in graph[current_node]:
        # 방문하지 않았다면 호출
        if not visited[adj_node]:
            dfs(adj_node)

graph = {
    1: [4,5],
    2: [3],
    3: [],
    4: [2,3],
    5: [4]
}

visited = [False for i in range(len(graph)+1)]

dfs(1)  # 1 4 2 3 5

 

 

DFS 순회 구현

  

    
    
    
    
  
from collections import defaultdict

adj_list = defaultdict(list)
visited = set()
result = []

def dfs(node):
    # 현재 노드 방문 표시
    visited.add(node)
    result.append(node)

    # 인접한 노드 탐색
    for adj_node in adj_list[node]:
        # 방문하지 않았다면 호출
        if adj_node not in visited:
            dfs(adj_node)


def solution(graph, start):
    for u,v in graph:
        adj_list[u].append(v)
    dfs(start)
    return result
    

# test case 1 - ['A', 'B', 'C', 'D', 'E']
graph = [['A','B'],['B','C'],['C','D'],['D','E']]
start = 'A'

# test case 2 - ['A', 'B', 'D', 'E', 'F', 'C']
graph = [['A','B'],['A','C'],['B','D'],['B','E'],['C','F'],['E','F']]
start = 'A'


print(solution(graph, start))