BFS와 DFS는 그래프 탐색 알고리즘 중 가장 기본적이고 대표적인 알고리즘입니다. 그렇지만 둘은 탐색 방법 및 동작 방식에서 차이가 있습니다.

BFS (Breadth-First Search)

BFS는 너비 우선 탐색 알고리즘으로, 그래프를 레벨 단위로 탐색하는 방식입니다. 즉, 시작 노드에서 출발하여 같은 레벨의 노드들을 먼저 탐색하고, 다음 레벨로 넘어갑니다. BFS는 FIFO(First In First Out) 방식의 큐를 이용하여 탐색합니다.

특징

• 시작 노드에서 가까운 노드를 우선적으로 탐색합니다.
• 레벨 순서대로 탐색하기 때문에 최단 경로 문제에 적합합니다.
• 모든 노드를 탐색할 때, 메모리 사용량이 많을 수 있습니다.

예시 코드 (Python)

from collections import deque

def bfs(graph, start):
    visited = []  # 방문한 노드를 저장할 리스트
    queue = deque([start])  # 큐에 시작 노드를 넣어줍니다.

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    
    return visited

DFS (Depth-First Search)

DFS는 깊이 우선 탐색 알고리즘으로, 그래프에서 한 경로의 끝까지 탐색한 뒤 다음 분기로 넘어가는 방식입니다. 즉, 한 경로를 끝까지 탐색하기 위해 스택이나 재귀 함수를 이용합니다.

특징

• 시작 노드에서 가능한한 멀리 있는 노드를 우선적으로 탐색합니다.
• 깊이 우선 탐색이기 때문에 최단 경로 문제에 적합하지 않습니다.
• 모든 노드를 탐색할 때, 메모리 사용량이 BFS보다 작을 수 있습니다.

예시 코드 (Python)

def dfs(graph, start, visited=[]):
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
    
    return visited

결론

BFS와 DFS는 그래프 탐색에서 중요한 알고리즘입니다. BFS는 너비 우선 탐색으로 가까운 노드부터 순서대로 탐색하며, DFS는 깊이 우선 탐색으로 한 경로를 끝까지 탐색하는 방식입니다. 어떠한 상황에 적합한지에 따라 알고리즘이 선택되어야 합니다.