탐색 알고리즘 - DFS와 BFS

BFS와 DFS는 모두 그래프를 탐색하는 방법이다.

그래프는 Node와 Node를 연결하는 Edge로 이루어진 자료구조이고

그래프를 탐색하는 것은 하나의 정점으로부터 연결된 모든 정점들을 한 번씩 차례대로 방문하는 것입니다.

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

https://developer-mac.tistory.com/64 (이미지 출처)

그림과 같이 하나의 정점에서 끝까지 탐색해 최하단의 정점까지 방문 후, 이전 갈림길로 돌아와 선택하지 않은 정점을 방문하는 식으로 탐색한다. DFS는 스택의 자료구조를 이용하고 구체적인 방문 과정은 다음과 같다.

 

1. 탐색 첫 노드를 스택에 삽입후 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문 처리, 인접 노드가 없다면 스택에서 최상단 노드를 꺼내기
3. 2를 수행할 수 없을때까지 반복

구현 방법

스택을 이용하여 구현, 실제로는 재귀함수를 이용하여 매우 간결히 구현가능 O(N) 시간 소요 가능

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는 큐(Queue) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

 

1. 탐색 첫 노드를 큐에 삽입후 방문처리
2. 큐에서 노드를 꺼내 인접노드중 방문하지 않은 모든 노드를 큐에 삽입하고 방문처리
3. 2를 수행 할 수 없을때 까지 반복

구현 방법

파이썬에서 큐를 deque을 이용하여 구현하는 것이 좋고 O(N)시간이 소요된다. 실제 수행 시간은 DFS보다 나은 편

from collections import deque

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 활용

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

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

 

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

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

 

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

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

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

 

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