깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)의 이해 및 Python 구현

탐색 알고리즘은 그래프나 트리 구조에서 유용하게 사용된다. 그 중 가장 많이 사용되는 두 가지 알고리즘이 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이다. 이 글에서는 DFS와 BFS의 개념, 특징, 그리고 Python을 사용한 구현 방법을 살펴보겠다.

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

개념

깊이 우선 탐색(Depth-First Search, DFS)은 가능한 한 깊숙이 들어가면서 탐색을 진행하는 방식입니다. 노드의 자식들을 우선적으로 방문한 후, 더 이상 방문할 노드가 없을 경우 이전 노드로 돌아가며 탐색을 이어갑니다. DFS는 재귀적인 방법 또는 스택 자료구조를 이용해 구현할 수 있습니다.

DFS의 특징

• 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
• 현재 정점에서 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아옴
• 스택 또는 재귀를 이용하여 구현
• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사
• 모든 노드를 방문하고자 할 때 주로 사용

DFS python 구현

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
  
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# DFS 실행
dfs(graph, 'A')

# 실행결과
A B D E F C

너비 우선 탐색 (BFS: Breadth-First Search)

개념

깊이 우선 탐색(Depth-First Search, DFS)은 가능한 한 깊숙이 들어가면서 탐색을 진행하는 방식입니다. 노드의 자식들을 우선적으로 방문한 후, 더 이상 방문할 노드가 없을 경우 이전 노드로 돌아가며 탐색을 이어갑니다. DFS는 재귀적인 방법 또는 스택 자료구조를 이용해 구현할 수 있습니다.

BFS의 특징

• 그래프의 넓이를 우선적으로 탐색하는 알고리즘
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐를 이용하여 구현
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
• 지도 어플리케이션에서 특정 위치까지의 최단거리 검색 등에 활용

BFS python 구현

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(graph[node])

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# BFS 실행
bfs(graph, 'A')

# 실행결과
A B C D E F

DFS VS BFS

특징	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 경로를 끝까지 탐색 후 다른 경로 탐색	인접한 노드를 모두 탐색 후 다음 레벨로 이동
사용 자료구조	스택 (재귀 사용 가능)	큐
경로 탐색	첫 번째 발견된 경로	최단 경로
메모리 사용량	그래프의 깊이에 비례	큐의 크기에 비례
시간 복잡도	O(V + E)	O(V + E)
사용 사례	미로 찾기, 순열 및 조합 생성	최단 경로 탐색 (예: 길찾기)