너비 우선 탐색 (BFS) vs 깊이 우선 탐색 (DFS)

너비 우선 탐색 (BFS)

BFS(Breadth-First Search)란, 한 지점에서 다른 지점들을 방문할 때, 너비를 우선으로 모든 지점을 방문하는 것

• 장점: 시작 지점으로부터 도착 지점까지의 최소 거리를 항상 구할 수 있다.
• 단점: DFS에 비해 더 많은 메모리를 사용한다.

출처: https://skilled.dev/course/breadth-first-search

특정 노드를 기준으로 “인접한” 노드를 우선적으로 탐색하는 방식이다. 즉, 시작 지점으로부터 가까운 노드를 우선적으로 방문하고, 멀수록 늦게 방문하게 된다. 이는 특히 거리 측정 알고리즘을 구현할 때 주로 사용될 수 있다.

 

주로 다차원 배열에서 특정 지점까지 걸리는 최소 시간을 구하는 문제에 BFS를 주로 사용할 수 있다. 코드로 구현하기 위해서는 Queue를 사용한다. BFS를 이용해 모든 지점을 방문하는 방법은 다음과 같다.

1. 비어있는 Queue에 시작 지점의 좌표를 입력한다.
2. 시작 지점을 방문하고, 이를 기록한다.
3. Queue의 Front에서 좌표를 꺼낸다.
4. 해당 지점에 인접한 다른 지점 모두를 Queue의 Rear에 넣는다.
   • 이때, 방문 여부를 판단하여 방문했던 지점은 Queue에 넣지 않는다.
5. Queue가 빌 때까지 2-4를 반복한다.

위와 같은 동작을 하는 Python 코드를 간단하게 작성하면 아래와 같다.

from collections import deque

def bfs(start_node):
    queue = deque([start_node])
    visited[start_node] = True

      while queue:
        cur_node = queue.popleft()
        for next_node in linked[cur_node]:
              if visited[next_node]:
                  continue
              visited[next_node] = True
              queue.append(next_node)

방문했던 지점을 다시 Queue에 넣지 않는 로직이 존재하므로, 칸의 수가 N개 일때 시간복잡도는 O(N)이 된다. 또한, Queue를 사용하므로, 반드시 시작 지점과의 거리순으로 방문하게 된다. visited 배열을 단순 True/False가 아니라 숫자를 이용해 기록한다면, 반드시 특정 위치에 도달한 순간이 최소 시간임이 보장되므로, 시작 지점으로부터의 거리를 관리할 수 있게 된다.

 

만약, 방문 표시를 Queue에 넣기 전에 남기지 않고, Queue에서 뺄 때 남긴다면 어떻게 될까?

from collections import deque

def bfs(start_node):
    queue = deque([start_node])

      while queue:
        cur_node = queue.popleft()
        visited[cur_node] = True

        for next_node in linked[cur_node]:
              if visited[next_node]:
                  continue
              queue.append(next_node)

위와 같이 구현을 한다면, 같은 지점이 여러 번 Queue에 들어가는 것을 방지 할 수 없다! 따라서, 시간 초과 or 메모리 초과가 발생할 가능성이 높아지게 된다.

⇒ 즉, BFS에서는 Queue에 넣기 전에 방문 표시를 남기도록 코드를 작성해야 한다.

 

깊이 우선 탐색 (DFS)

DFS(Depth-First Search)란, 한 지점에서 다른 지점들을 방문할 때, 깊이를 우선으로 모든 지점을 방문하는 것

• 장점: BFS에 비해 목표 지점에 더 빠르게 도달할 수 있다.
• 단점: 최단 경로를 보장하지 않으며, 정답이 없는 경로에 깊이 빠질 위험이 있다.

출처: https://skilled.dev/course/depth-first-search

특정 노드부터 “가장 깊은 노드”까지 우선적으로 탐색하고, 막혔을 때 이전으로 되돌아와 다음 경로를 탐색하는 방식이다. 즉, 시작 지점부터 시작하여 가장 먼 노드까지의 한 가지 경로를 우선적으로 탐색하고, 해당 경로를 모두 탐색한 뒤에야 다른 경로를 탐색한다.

 

대부분 BFS로 풀 수 있는 문제는 DFS로 해결할 수 있다. 그러나, 최단 거리 측정을 할 수 없다는 단점이 있어, 탐색 문제에서는 BFS가 조금 더 광범위하게 사용된다. DFS를 코드로 구현하기 위해서는 Stack을 사용하거나, 재귀적인 방식으로 구현할 수 있다. Stack을 이용한 DFS로 모든 지점을 방문하는 방법은 다음과 같다.

1. 비어있는 Stack에 시작 지점의 좌표를 입력한다.
2. 시작 지점을 방문하고, 이를 기록한다.
3. Stack의 Top에서 좌표를 꺼낸다.
4. 해당 지점에 인접한 다른 지점 모두를 Stack의 Top에 넣는다.
   • 이때, 방문 여부를 판단하여 방문했던 지점은 Stack에 넣지 않는다.
5. Stack이 빌 때까지 2-4를 반복한다.

위와 같은 동작을 하는 Python 코드를 간단하게 작성하면 아래와 같다.

from collections import deque

def dfs(start_node):
    stack = deque([start_node])
    visited[start_node] = True

      while queue:
        cur_node = stack.pop()
        for next_node in linked[cur_node]:
              if visited[next_node]:
                  continue
              visited[next_node] = True
              stack.append(next_node)

BFS의 구현 방식에서 Queue가 Stack으로 대체된 형식이다. 따라서 시간복잡도는 BFS와 동일하게 O(N)이다. DFS는 BFS와 달리, 특정 시점에 처음으로 방문한 것이 최소 시간임을 보장하지 못하므로 최소 시간을 구하는 문제에 이용하기는 어렵다.

 

재귀를 이용해서도 DFS를 구현할 수 있다.

from collections import deque

def dfs(start_node):
    visited[start_node] = True

    for next_node in linked[start_node]:
        if visited[next_node]:
            continue
        dfs(next_node)

이러한 구현 방식은 백트래킹과 같이 재귀적으로 경우의 수를 탐색할 때 많이 사용될 수 있다.

References

• 바킹독의 실전 알고리즘 0x09강: BFS
• 바킹독의 실전 알고리즘 0x0A강: DFS
• https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
• https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html