[Python] 너비 우선 탐색(BFS, Breadth-First Search), 깊이 우선 탐색(DFS, Depth Frist Search)

핵심 개념

DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘이다. DFS는 한 방향으로 끝까지 탐색한 후 돌아오는 방식이며, BFS는 가까운 노드부터 탐색하는 방식이다.

 

시간 복잡도

두 탐색 방법의 시간 복잡도는 일반적으로 \( O(V + E) \)이다.

 

여기서 \( V \)는 vertex(or 노드) 개수, \( E \)는 edge(간선) 개수이다. DFS와 BFS 모두 모든 노드를 방문하기 때문에 그래프의 크기에 따라 탐색 시간이 결정된다.

 

동작방식 & 구현

Fig 1. BFS, DFS

 

DFS

Fig 2. DFS

1. 시작 노드에서 한 방향으로 갈 수 있는 만큼 탐색한다.
2. 더 이상 이동할 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색한다.
3. 모든 노드를 방문할 때까지 반복한다.

 

BFS

Fig 3. BFS

1. 시작 노드에서 가까운 노드부터 탐색한다.
2. 큐(Queue)를 활용해 방문할 노드를 관리한다.
3. 모든 노드를 방문할 때까지 반복한다.

 

활용 가능한 문제 유형

DFS

• 경로 찾기: 미로 탐색, 게임 맵 탐색 등
• 백트래킹: N-Queen 문제, 부분 수열 찾기 등
• 사이클 탐색: 그래프 내 사이클 존재 여부 확인

 

BFS

• 최단 거리 문제: 미로 최단 거리, 네트워크 거리 계산
• 최소 이동 횟수 문제: 퍼즐 문제, 말 이동 횟수 등
• 레벨 탐색: 트리의 특정 깊이에 있는 노드 탐색

 

예제 코드(Python)

DFS

def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=' ')
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# 예제 실행
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}
visited = set()
dfs(graph, 'A', visited)

 

BFS

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            queue.extend(graph[node])

# 예제 실행
bfs(graph, 'A')

 

결론

DFS와 BFS는 그래프 탐색의 핵심 알고리즘이다. DFS는 백트래킹과 재귀적 탐색에 유리하며, BFS는 최단 거리 문제에서 강력한 성능을 발휘한다. 문제의 특성에 따라 적절한 탐색 방법을 선택하는 것이 중요하다.

 

---

 

참고 자료

 

https://velog.io/@vagabondms/DFS-vs-BFS

 

https://oliviagallucci.com/graph-algorithm-basics-bfs-and-dfs/#dfs

 

https://www.batoi.com/blogs/developers/introduction-data-structures-tree-60660d6769715