[Algorithm] DFS & BFS

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

DFS와 BFS를 공부하기 전, 먼저 스택과 큐, 재귀함수에 대한 이해가 필요하다.

 

스택 (Stack)

• FILO (First In, Last Out)
• 먼저 들어온 데이터가 나중에 나가는 선입후출의 구조
• Python에서 스택을 사용할 경우에는 별도의 라이브러리가 필요하지 않다.
  • 기본 리스트에서 append()와 pop() 메서드를 사용하면 스택 자료구조와 동일하게 동작한다.
  • append() : 리스트의 가장 뒤쪽에 데이터 삽입
  • pop() : 리스트의 가장 뒤쪽에서 데이터를 삭제하고 리턴

 

큐 (Queue)

• FIFO (First In, First Out)
• 먼저 들어온 데이터가 먼저 나가는 선입선출의 구조
• Python에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 사용하는 것이 좋다.
  • 리스트를 사용해도 큐 자료구조를 구현할 수는 있지만 시간 복잡도가 높다.
  • deque는 스택과 큐의 장점을 모두 채택한 것
  • 데이터를 삽입, 삭제하는 속도가 리스트에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 간단하다.
  • append() : 리스트에서 append와 동일
  • popleft() : 가장 왼쪽의 데이터를 꺼낸다.

 

재귀함수 (Recursive Function)

• 자기 자신을 다시 호출하는 함수
• 파이썬에는 최대 재귀 깊이 제한이 있기 때문에 무한한 재귀 호출을 하면 에러가 발생한다.
• 재귀 함수의 종료 조건을 명시해야 한다.

---

DFS (Depth-First Search)

• 깊이 우선 탐색
• 스택 자료구조를 이용하여 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• 재귀 함수를 사용하면 스택을 사용하지 않아도 된다.

 

동작 과정

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

def dfs(graph, v, visited):
  # 방문 표시
  visited[v] = True
  print(v, end=' ')
  # 인접 노드들 중
  for i in graph[v]:
    # 방문하지 않은 노드가 있다면
    if not visited[i]:
      # 해당 노드를 방문하고 탐색
      dfs(graph, i, visited)

 

BFS (Breadth-First Search)

• 너비 우선 탐색
• 큐 자료구조를 이용해서 가까운 노드부터 탐색하는 알고리즘이다.
• 보통 DFS보다 BFS가 조금 더 빠르다.

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

from collections import deque

def bfs(graph, start, visited):
  # Queue 구현을 위해 collectios의 deque 시영
  # 시작 노드를 큐에 삽입
  queue = deque([start])
  # 현재 노드 방문 처리
  visited[start] = True

  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 꺼내 출력
    v = queue.popleft()
    print(v, end=' ')
    # 해당 노드의 인접 노드 중에서
    for i in graph[v]:
      # 방문하지 않은 노드가 있다면
      if not visited[i]:
        # 큐에 삽입하고 방 처리
        queue.append(i)
        visited[i] = True

 

시간 복잡도

DFS와 BFS 모두 \(O(N)\)의 시간 복잡도를 갖는다.

• 인접 리스트 : \(O(N + E)\)
  • 인접한 노드의 정보만을 저장하기 때문에 간선의 개수인 E의 두 배만큼의 시간이 소요된다.(하나의 간선마다 두 개의 노드가 있기 때문) 따라서 \(O(N + 2*E) = O(N + E)\)이다.
• 인접 행렬 : \(O(N^2)\)
  • N개의 모든 노드에 대해서 두 노드가 연결되어 있는지 확인해야 하므로 이중 for문을 사용해야 한다.

 

DFS vs BFS

• DFS
  • 장점
    • 현 경로 상의 노드들만 기억하기 때문에 적은 메모리를 사용한다.
    • 목표 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 탐색할 수 있다.
  • 단점
    • 답이 아닌 경로가 매우 깊다면 그 경로에 깊이 빠질 우려가 있다.
    • 찾은 해가 최단 경로라는 보장이 없다.
  • 각각의 경로마다 특징을 저장해야 하는 문제
  • 대상 그래프가 매우 클 때
• BFS
  • 장점
    • 모든 경로를 탐색하기 때문에 여러 해가 있을 경우에도 최단 경로임을 보장한다.
    • 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.
    • 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.
  • 단점
    • 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음 탐색 노드를 저장하기 때문에 노드의 수가 많을수록 더 큰 메모리 공간이 필요하다.
    • 노드의 수가 많아지면 탐색해야 하는 노드가 많아지기 때문에 비효율적이다.
  • 최단 거리를 구해야 하는 문제
  • 탐색 규모가 크지 않고 시작 지점으로부터 원하는 대상이 멀지 않은 경우