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

셔노·2023년 4월 23일

자료구조 알고리즘

목록 보기

12/16

그래프는 연결된 노드와 간선으로 이루어진 자료구조이다. 그래프는 다양한 분야에서 활용되며, 그래프를 탐색하는 알고리즘은 이러한 분야에서 중요한 역할을 한다.

DFS (Depth-First Search)

DFS는 깊이 우선 탐색 알고리즘으로, 스택이나 재귀 호출을 이용하여 구현할 수 있다. DFS는 시작 노드에서부터 한 경로를 따라 최대한 깊게 탐색한 후, 다른 경로를 탐색한다. 이러한 방식으로 탐색을 진행하면서 방문한 노드를 스택에 저장하고, 더이상 탐색할 수 없을 때 스택에서 노드를 꺼내어 역순으로 출력한다. DFS는 그래프의 구조를 파악하는데 유용하며, 미로 찾기 등의 문제를 해결하는데 활용된다.

DFS를 이용하여 그래프를 탐색할 때는, 방문한 노드를 기록해야 한다. 이를 위해 visited 리스트를 만들어서 방문한 노드를 저장한다. DFS에서는 스택 또는 재귀 함수를 이용하여 노드를 방문하게 된다. 스택이나 재귀 함수가 호출될 때마다, 해당 노드와 연결된 인접 노드 중에서 방문하지 않은 노드를 스택에 저장하고, 그 노드를 방문한다. 이러한 과정을 반복하여 그래프를 탐색하게 된다.

구현 예시 (인접 리스트를 이용한 DFS)

def dfs(graph, start):
    visited = [] # 방문한 노드를 저장할 리스트
    stack = [start] # 시작 노드를 스택에 저장
    while stack:
        node = stack.pop() # 스택에서 노드를 꺼냄
        if node not in visited:
            visited.append(node) # 방문한 노드를 저장
            stack.extend(graph[node] - set(visited)) # 방문하지 않은 인접 노드를 스택에 추가
    return visited

BFS (Breadth-First Search)

BFS는 너비 우선 탐색 알고리즘으로, 큐를 이용하여 구현할 수 있다. BFS는 시작 노드에서부터 인접한 노드를 모두 탐색한 후, 다음 노드로 이동한다. 이러한 방식으로 탐색을 진행하면서 방문한 노드를 큐에 저장하고, 먼저 저장된 노드부터 출력한다. BFS는 최단 경로를 찾거나, 노드 간 최단 거리 등을 구하는데 활용된다.

BFS를 이용하여 그래프를 탐색할 때는, 방문한 노드를 기록하고, 인접한 노드를 큐에 저장한다. 큐에서 노드를 꺼낸 후, 해당 노드와 연결된 인접 노드 중에서 방문하지 않은 노드를 큐에 추가한다. 이러한 과정을 반복하여 그래프를 탐색하게 된다.

구현 예시 (인접 리스트를 이용한 BFS)

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] - set(visited)) # 방문하지 않은 인접 노드를 큐에 추가
    return visited