[알고리즘 이론] 탐색 알고리즘 - DFS / BFS

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다.

 

깊이 우선 탐색(DFS, Depth - First Search)

DFS는 Depth - First Search, 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

그림에서와 같이 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문하는 식으로 탐색한다. DFS는 스택(Stack) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

 

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

 

※ DFS의 구현

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다.

실제로는 스택을 쓰지 않고 재귀 함수를 이용하여 매우 간결하게 구현할 수 있으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다.

# DFS 메소드 정의
def dfs(graph, v, visited):
  visited[v] = True
  print(v, end = '')

  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

graph = [] # 그래프를 표현하는 인접 리스트(2차원 리스트)
visited = [] # 각 노드가 방문된 정보를 표현하는 1차원 리스트

dfs(graph, 1, visited) # dfs 함수 호출

---

너비 우선 탐색(BFS, Breadth - First Search)

BFS는 Breadth - First Search, 너비 우선 탐색이라고도 부르며, 그래프와 트리의 가까운 노드부터 탐색하는 알고리즘이다.

그림에서와 같이 루트 노드와 같은 거리에 있는 노드를 우선으로 방문하며 탐색한다.

BFS는 큐(Queue) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

 

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

 

※ BFS의 구현

BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 큐를 구현함에 있어 이전 포스트에서 언급한 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

from collections import deque
# BFS 메소드 정의

def bfs(graph, start, visited):
  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

graph = [] # 그래프를 표현하는 인접 리스트(2차원 리스트)
visited = [] # 각 노드가 방문된 정보를 표현하는 1차원 리스트

bfs(graph, 1, visited) # bfs 함수 호출

---

DFS와 BFS 비교

 

	DFS	BFS
탐색 과정	현재 정점에서 갈 수 있는 끝까지 방문하며 탐색	현재 정점에 연결된 가까운 점들부터 탐색
구현 방법	스택 또는 재귀 함수로 구현	큐 자료구조 이용

 

※ DFS와 BFS의 시간 복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작한다고 기억하면 된다. 

N이 노드의 개수, E가 간선의 개수일 때
인접 리스트: O(N + E)
인접 행렬: O(N^2)

일반적으로 인접 리스트 방식이 더 효율적이다.

 

문제의 특징 별 DFS / BFS 활용

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관이 없다. 

 

2. 경로의 특징을 저장해둬야 하는 문제

예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)

 

3. 최단거리를 구하는 문제

미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다.

왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

 

이외에도 검색 대상 그래프가 정말 크다면 DFS를 고려하고 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려하는 등으로 더 생각해볼 수 있다. 

 

DFS / BFS 구현 기본 문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)