검색 알고리즘 - 깊이 우선 검색(DFS)

DFS(Depth-First Search)

DFS는 트리나 그래프 데이터 구조를 탐색하는 데 사용되는 기본 검색 알고리즘이다. 선택한 노드(트리의 루트 또는 그래프의 모든 노드)에서 시작하여 각 분기를 따라 가능한 한 멀리 탐색한다.

DFS 작동 방식

• 선택한 노드에서 시작: 시작점으로 노드를 선택한다.
• 노드를 방문으로 표시: 알고리즘이 무한 루프에 빠지는 것을 방지하기 위한 것이다.
• 방문하지 않은 이웃 탐색
  • 현재 노드의 방문하지 않은 이웃을 선택한다.
  • 해당 이웃 노드를 방문했다고 표시한다.
  • 해당 이웃에 대해 DFS를 반복적으로 수행한다.
• 방문하지 않은 이웃이 없는 경우 역추적: 현재 노드에 방문하지 않은 이웃이 없으면 상위 노드로 역추적하고 그곳에서 방문하지 않은 이웃을 확인한다.
• 모든 노드를 방문하거나 목표에 도달할 때까지 반복: 도달 가능한 모든 노드를 방문하거나 특정 목표(예: 특정 노드 찾기)가 달성될 때까지 프로세스가 계속된다.

장단점

• 장점
  • 메모리 효율성: DFS는 BFS(Breadth-First Search)에 비해 상대적으로 적은 메모리가 필요하다. 이는 루트 노드에서 현재 노드까지의 경로에 있는 노드 스택만 저장하기 때문이다.
  • 경로 찾기: 가능한 모든 경로를 탐색하거나 특정 목표 노드를 찾아야 하는 솔루션을 찾아야 하는 시나리오에 유용하다.
  • 주기 감지: DFS는 그래프에서 주기를 감지하는 데 특히 유용하므로 운영 체제의 종속성 분석이나 교착 상태 감지와 같은 애플리케이션에 유용하다.
• 단점
  • 비최적 솔루션: DFS는 노드까지의 최단 경로를 보장하지 않는다.
  • 무한 루프: 방문한 노드를 표시하는 데 주의를 기울이지 않으면 DFS가 무한 루프에 빠질 수 있다.
  • 스택 오버플로: DFS의 재귀적 구현은 트리 또는 그래프가 매우 깊은 경우 스택 오버플로로 이어질 수 있다.

복잡도

• 시간 복잡도:
  • V(Vertex)는 정점 수이고 E(Edge)는 그래프의 간선 수
  • 인접 행렬: O(V²)
  • 인접 리스트: O(V + E)
• 공간 복잡도: O(V)

인접 행렬

• 인접 행렬: 그래프를 표현하는 데 사용되는 정사각 행렬이다. 그래프에서 정점 쌍이 인접해 있는지를 나타낸다.
  • 장점
    • 간선 탐색 용이: 특정 두 정점 사이에 간선이 있는지 없는지를 O(1) 시간 내에 쉽게 확인할 수 있다.
    • 구현의 단순성: 2차원 배열을 사용하기 때문에 구현이 간단하고 직관적이다.
  • 단점
    • 공간 낭비: 항상 정점 수의 제곱에 비례하는 공간을 사용하므로 공간 비효율적이다.
    • 간선 추가/제거 시간 비효율: 간선을 추가하거나 제거할 때, 배열의 특정 위치를 변경하는 것은 빠르지만, 정점을 추가하거나 제거할 때는 전체 배열의 크기를 조정해야 하므로 비효율적이다.

graph = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 0],
    [0, 1, 0, 0]
]

인접 리스트

• 인접 리스트: 그래프를 목록의 배열로 나타낸다. 배열의 인덱스는 꼭짓점을 나타내고 연결된 목록의 각 요소는 꼭짓점과 가장자리를 형성하는 다른 꼭짓점을 나타낸다.
  • 장점
    • 공간 효율성: 간선의 수에 비례하는 공간만을 사용하기 때문에 공간을 효율적으로 사용한다.
    • 간선 추가 및 제거 용이: 새로운 간선이나 정점을 추가하거나 제거하는 작업이 행렬에 비해 간단하고 빠르다.
    • 인접한 정점 탐색: 특정 정점에 인접한 모든 정점을 탐색하는 작업이 빠르다.
  • 단점
    • 특정 간선 탐색: 두 정점 사이에 간선이 존재하는지 확인하기 위해서는 해당 정점의 인접 리스트 전체를 탐색해야 하므로 시간이 더 걸릴 수 있다.

graph = [['B', 'C'], ['A', 'C', 'D'], ['A', 'B'], ['B']]

예제 코드 - 인접 행렬을 사용한 DFS

class Graph:
  def __init__(self, size):
    self.size = size
    self.adj_matrix = [[0] * size for _ in range(size)]

  def add_edge(self, v1, v2):
    if 0 <= v1 < self.size and 0 <= v2 < self.size:
      self.adj_matrix[v1][v2] = 1
      self.adj_matrix[v2][v1] = 1
    else:
        print("Invalid vertices: %d, %d" % (v1, v2))

  def dfs(self, start, visited=None):
    if visited is None:
      visited = set()

    visited.add(start)
    print(start, end=' ')
    for i in range(self.size):
      if self.adj_matrix[start][i] == 1 and i not in visited:
        self.dfs(i, visited)

graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)

print("DFS Traversal:")
graph.dfs(0) # Output : 0 1 3 2 4