[CS기초] DFS(Depth-First Search), BFS(Breadth-First Search)

DFS, BFS 개요

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리 같은 자료구조에서 원하는 정보를 찾기 위해 모든 정점이나 경로를 방문하며 탐색하는 대표적인 순회 알고리즘입니다. 각각 스택(또는 스택을 활용한 재귀)과 큐를 기반으로 탐색 순서를 제어합니다.

 

때문에 DFS, BFS의 원리를 이해하기 위해 먼저 스택, 큐, 재귀함수 그리고 그래프에 대해 알고 있어야 합니다. 이미 알고 있으시다면 넘어가도 좋고, 혹시 한 번 더 선행 개념에 대한 이해가 필요하신 분들은 아래의 글을 참고해보시면 좋을 것 같습니다.

 

스택, 큐

https://just-live.tistory.com/entry/CS%EA%B8%B0%EC%B4%88-%EC%8A%A4%ED%83%9DStack-%ED%81%90Queue

[CS기초] 스택(Stack), 큐(Queue)

재귀함수

https://just-live.tistory.com/entry/CS%EA%B8%B0%EC%B4%88-%EB%B0%98%EB%B3%B5%EB%AC%B8%EA%B3%BC-%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98#%EC%9E%AC%EA%B7%80%20%ED%95%A8%EC%88%98%20(Recursion%20Function)-1-1

[CS기초] 반복문(Loop), 재귀 함수(Recursion Function)

그래프

https://just-live.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84Graph

[자료구조] 그래프(Graph)

 

 

DFS

DFS(Depth-First Search)는 그래프에서 깊이(멀리 있는 노드)를 우선적으로 탐색하는 알고리즘입니다. 한 경로를 가능한 한 깊이 따라간 뒤, 더 이상 진행할 수 없으면 이전 분기점으로 되돌아가 다른 경로를 탐색합니다.

 

DFS의 특징

스택 자료구조를 활용

DFS는 스택(Stack)을 사용하여 정점(노드)을 방문하는데요. 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 스택에 넣는다.
2. 스택의 최상단에서 노드를 하나 꺼내 방문 처리한다.
3. 방문한 노드의 인접 노드 중 아직 방문하지 않은 노드를 찾아 스택에 넣는다. 
4. 더 이상 방문할 노드가 없을 때까지 2~3번의 과정을 반복한다.

※ DFS나 BFS 같은 그래프 탐색 알고리즘은 무한 루프 방지를 위해, 방문 여부를 저장하는 배열이 필요합니다.

재귀 호출을 활용해 간단하게 구현 가능

스택을 사용하는 대신, DFS는 재귀 호출을 통해 보다 간결하게 구현할 수 있습니다. 일반적으로 재귀 호출을 사용한 코드가 더 직관적이고 간결하게 작성됩니다.

시간 복잡도는 O(V+E)

DFS는 모든 정점(V)과 간선(E)을 한 번씩 방문하기 때문에, 시간 복잡도는 총 O(V+E)입니다.

모든 경로 탐색에 유리

경로의 수를 세거나, 단순히 정답 여부를 확인할 때 DFS는 BFS보다 더 자연스럽고 구현도 간단한데요. 특히 트리 구조에서 전위(pre-order), 중위(in-order), 후위(post-order) 순회와 같은 노드 방문 순서를 정할 때 매우 유용합니다.

백트래킹 활용 가능

모든 방향으로 평등하게 탐색이 퍼져나가는 BFS와 달리, DFS는 조건에 따라 불필요한 경로를 중간에 포기하고 되돌아가며 효율적으로 탐색하는 백트래킹(Backtracking) 기법을 적용할 수 있습니다. 즉, 백트래킹은 DFS의 일종이라고 볼 수 있습니다.

 

파이썬에서 DFS의 구현

n = 8
start_node = 1
graph = [[],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 6, 8],
         [1, 7]
        ]

def dfs(graph, node, visited):
    # 현재 노드 방문 처리
    visited[node] = True
    print(node, end=' ')
    # 현재 노드의 방문하지 않은 인접 노드를 재귀적으로 방문
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)

visited = [False] * (n+1)
dfs(graph, start_node, visited)     # 출력 : 1 2 7 6 8 3 4 5

 

 

BFS

BFS(Breadth-First Search)는 너비를 우선하여 탐색하는 알고리즘으로, 가까운 노드를 우선적으로 탐색합니다. 인접한 노드부터 순서대로 방문하기 때문에 마치 수면 위에 파동이 퍼지듯 동작합니다.

 

BFS의 특징

큐 자료구조를 활용

BFS는 FIFO(선입선출, First-In First-Out) 방식의 큐(Queue)를 사용하여 탐색할 노드를 관리하는데요. 이를 통해 주변 노드부터 차례로 방문하기 때문에, 한쪽 방향으로 깊이 들어가는 DFS(스택 또는 재귀 호출 사용)와 구현 방식에서 큰 차이를 보입니다.

 

큐를 활용한 BFS의 탐색 과정은 다음과 같습니다.

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

시간 복잡도는 O(V+E)

DFS와 마찬가지로 모든 정점(V)과 간선(E)을 한 번씩만 탐색하므로, 시간 복잡도는 동일하게 O(V+E)입니다.

최단 경로 탐색과 계층 단위 순회에 유리

BFS는 가까운 노드부터 탐색하기 때문에 처음 도달한 노드가 곧 최단 경로를 의미합니다. 따라서 가중치가 없는 그래프에서 최단 거리나 최소 이동 횟수를 찾는 최단 경로 문제에 많이 활용됩니다.

 

또한 탐색이 계층(레벨) 단위로 진행되기 때문에 트리의 레벨 단위 순회(Level-Order Traversal)에 매우 적합합니다.

 

파이썬에서 BFS의 구현

from collections import deque

n = 8
start_node = 1
graph = [[],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 6, 8],
         [1, 7]
        ]

def bfs(graph, start_node, visited):
    q = deque()
    q.append(start_node)
    # 시작 노드 방문 처리
    visited[start_node] = True
    
    while q:
        now = q.popleft()
        print(now, end=' ')
        # 현재 노드의 방문하지 않은 인접 노드를 방문 처리 후 큐에 추가
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

visited = [False] * (n+1)
bfs(graph, start_node, visited)     # 출력 : 1 2 3 8 7 4 5 6