[알고리즘][개념] DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)

https://devuna.tistory.com/32, 튜나 개발일기를 참고하였습니다. 

 

여러 자료구조 중 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색, DFS와 너비 우선 탐색인 BFS가 존재한다. 

여기서 말하는 그래프란 node와 edge로 구성된 자료구조를 말한다. 이 중 방향성이 있는 비순환 그래프를 트리라고 말한다. 

이런 그래프를 탐색한다는 의미는 하나의 정점으로부터 시작하여 차례대로 모든 정점을 하나씩 방문하는 것을 의미한다. 

 

코테 문제 중 일부는 이런 search 기법을 잘 구현해야하기에 DFS와 BFS의 개념을 알아보고 python으로 주어진 그래프를 간단히 탐색해보는 예제코드를 작성해보려고 한다. 

 

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

: 우선 최대한 깊이 내려간 뒤에, 더 이상 갈 수 없다면 옆으로 가자!

출처 https://developer-mac.tistory.com/64

깊이 우선 탐색이란 위의 이미지에서 볼 수 있듯이, 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게(깊숙히 끝까지) 탐색하는 방법이다. 

스택 또는 재귀함수로 구현한다.

 

아래의 특징이 있다. 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

너비 우선 탐색(BFS, Breadth-First Search): 1층 1층 보자..!(layer 단으로 보자)

출처 https://developer-mac.tistory.com/64 루

루트 노드(혹은 다른 임의의 노드)에서 시작해석 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점들, 즉 이웃 노드들을 우선 방문하는 방법이다. 큐를 이용해서 구현한다. 

 

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다. 

DFS와 BFS 비교 

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

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

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

둘 중 편한 것을 사용하시면 됩니다.

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

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

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도 
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

간단한 코드 구현(python)

트리 구현

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, node):
        self.children.append(node)
        
# 트리 생성
root = TreeNode(1)
child_1 = TreeNode(2)
child_2 = TreeNode(3)
child_3 = TreeNode(4)

root.add_child(child_1)
root.add_child(child_2)
root.add_child(child_3)

child_1.add_child(TreeNode(5))
child_3.add_child(TreeNode(6))
child_3.add_child(TreeNode(7))

 

구현된 트리는 아래와 같습니다.

       1
     / | \
    2  3  4
   /      / \
  5      6   7

DFS 알고리즘: 

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

def dfs(node):
    if node is None:
        return
    print(node.value, end=" ")  # 현재 노드 출력
    for child in node.children:
        dfs(child)  # 자식 노드에 대해 재귀 호출

2. 스택을 이용한 구현

스택의 경우 LIFO를 따름으로 이를 이용. 아래의 방식으로 작동

1. 루트 노드를 스택에 추가합니다.
2. 스택에서 노드를 꺼내고 그 노드를 방문합니다.
3. 꺼낸 노드의 자식들을 스택에 추가하는데, 자식을 오른쪽에서 왼쪽 순서로 넣어야 스택에서 꺼낼 때 왼쪽 자식부터 방문하게 됩니다.
4. 스택이 비어있을 때까지 위 과정을 반복합니다.

def dfs_stack(root):
    if root is None:
        return
    
    stack = [root]  # 스택에 루트 노드를 넣음
    
    while stack:
        node = stack.pop()  # 스택에서 가장 위의 노드를 꺼냄
        print(node.value, end=" ")  # 현재 노드 출력
        
        # 자식 노드를 스택에 추가 (반대로 추가해야 왼쪽부터 탐색됨)
        # 자식들을 오른쪽에서 왼쪽 순으로 스택에 넣어야 왼쪽부터 탐색됨
        for child in reversed(node.children):
            stack.append(child)

 

1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7 순서로 탐색함 

BFS 알고리즘: 

큐를 이용하여 구현. 큐의 경우 FIFO 임으로 탐색할 노드를 큐에 넣고, 이후 그 다음 자식 노드들을 큐에 차례대로 넣어가며 탐색한다. 

from collections import deque

def bfs(root):
    if root is None:
        return
    queue = deque([root])  # 큐에 루트 노드를 삽입
    while queue:
        node = queue.popleft()  # 큐의 앞에서 노드를 꺼내고 출력
        print(node.value, end=" ")
        queue.extend(node.children)  # 현재 노드의 자식들을 큐에 삽입

 

BFS는 트리의 레벨 순서대로 탐색합니다. 먼저 루트 노드 1을 방문하고, 그 다음 레벨에서 2, 3, 4를 방문한 후, 그다음 레벨에서 5, 6, 7을 방문합니다. BFS 탐색 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7입니다