어제 BFS에 대해서 다시 정리해 보았다. 이제 BFS와 쌍두마차를 이루고 있는 탐색 방법인 'DFS'를 간단하게 정리해 보도록 하자.

DFS

Depth - First Search의 약자로 그래프를 탐색 할 때 깊이를 우선적으로 탐색하는 방법을 의미하며 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다

• 위의 설명과 같이 깊이를 우선으로 탐색해 나간다.

구현 방법

구현 방법은 크게 2가지를 이용하여 구현 가능하다.

1. stack을 이용한 구현

2. 재귀함수를 이용한 구현

stack을 이용한 구현

#이때 graph는 인접 리스트로 구현이 되어있다.

def dfs(graph, start):
    stack = [start]
    visited = []

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            stack.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

    return visited

재귀를 이용한 구현

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

시간 복잡도

• 인접 리스트 : O(V+E)
  • 해당 정점과 연결된 정점들만 확인 한다.

• 인접 행렬 : O(V^2)
  • 해당 정점과 모든 정점이 연결 되어있는지 전부 확인 하기 때문에

장단점

• 장점 : BFS보다 메모리를 덜 차지 한다.

  • 현재 경로만 저장 하면 되어 메모리를 덜 차지 한다.
    (ex. A-> B -> C에서 C가 더이상 인접한 노드가 없으면 B로 백트래킹을 하기 때문에 현재 경로만 저장하면 된다.)

• 단점

  • 해당 경로가 최단 경로가 아닐 가능성이 있다.
  • 해가 아닌 경로가 매우 깊게 있을 경우 시간 복잡도가 높게 된다.