[알고리즘] 깊이우선탐색 (DFS : Depth First Search)

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

• 한 노드에서 그 노드의 깊이에 있는 모든 노드들을 탐색한 후에 다음 너비에 있는 노드를 탐색하는 알고리즘이다. (BFS와 반대)
  

깊이우선탐색(DFS)의 특징

• 스택으로 구현할 수도 있지만 자기 자신을 호출하는 재귀를 통해 구현할 수도 있다.
• 탐색한 노드를 방문했는지의 여부를 반드시 검사해야한다.

깊이우선탐색(DFS)의 원리

출처 : 위키피디아

깊이우선탐색(DFS) 파이썬 코드 구현

1. Stack을 이용한 DFS

def DFS(graph, start_node):
    visited = []
    stack = [start_node]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

2. 재귀를 이용한 DFS

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