[알고리즘] DFS와 BFS

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

그래프 탐색 알고리즘의 대표적인 예로 이 알고리즘들은 그래프, 트리, 네트워크 등의 자료구조를 탐색하는 데 사용한다.

 

그래프는 노드(정점)와 노드 간의 연결선(간선)으로 이루어진 자료구조를 말한다.

• 노드 (Vertex) : 그래프에서 하나의 개체를 말하며 정점이라고도 한다.
• 간선 (Edge) : 두 노드를 연결하는 선
• 인접 노드 : 특정 노드와 직접 연결된 노드

---

DFS (깊이 우선 탐색)

시작 노드에서부터 한 방향으로 갈 수 있을 만큼 깊이 내려가며 탐색을 진행한다. 그 깊이의 노드를 모두 탐색한 후 더 이상 갈 수 없게 되면 이전 정점으로 돌아가 다음 노드를 탐색하는 방식이다.

 

탐색 과정

1. 시작 노드에서 출발하여 다음 노드로 이동
2. 더 이상 방문하지 않은 인접 노드가 없을 때까지 깊이 내려가며 방문
3. 방문할 인접 노드가 없으면 직전 노드로 돌아가 다른 인접 노드를 탐색
4. 모든 노드를 방문할 때까지 이 과정을 반복

 

DFS의 특징

• 장점 : 모든 경로를 탐색하거나 특정 경로를 찾는 데 유리하다.
• 단점 : 탐색할 깊이에 따라 재귀 호출이 많아질 수 있으므로 깊이가 깊어질수록 메모리 사용이 많아질 수 있다.

 

 

DFS 코드

• 재귀 사용

def dfs_recursive(graph, node, visited):
    visited[node] = True
    print(node, end=' ')  # 방문한 노드를 출력

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

# 그래프를 인접 리스트로 표현 (0번 노드부터 시작)
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1, 5],
    4: [1, 2],
    5: [3]
}

visited = [False] * len(graph)

# DFS 시작 (시작 노드는 0)
dfs_recursive(graph, 0, visited)

• 스택 사용 

def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            print(node, end=' ')  # 방문한 노드를 출력

            # 인접한 노드를 스택에 추가 (역순으로 넣으면 방문 순서가 맞음)
            for neighbor in reversed(graph[node]):
                if not visited[neighbor]:
                    stack.append(neighbor)

# DFS 시작
dfs_stack(graph, 0)

 

---

BFS 구현 (너비 우선 탐색)

시작 노드에서 가까운 노드부터 탐색을 진행한다. 인접한 모든 노드를 탐색한 후 그 다음 깊이의 노드를 탐색하는 방식이다.

 

탐색 과정

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드를 모두 큐에 넣고 방문 처리
3. 큐가 빌 때까지 이 과정을 반복

 

BFS의 특징

• 장점 : 간선의 가중치가 동일한 그래프에서 최단 경로를 찾는 데 유리하다.
• 단점 : 너비를 우선으로 탐색하기 때문에 한꺼번에 많은 노드를 저장해야 하므로 노드가 많을 경우 메모리 사용이 많아질 수 있다.

 

 

BFS 구현

• 큐 사용

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if not visited[node]:
            visited[node] = True
            print(node, end=' ')  # 방문한 노드를 출력

            # 인접한 노드를 큐에 추가
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    queue.append(neighbor)

# BFS 시작
bfs(graph, 0)

비교

종류	DFS	BFS
탐색 순서	깊이 우선	너비 우선
자료구조	재귀, 스택	큐
실전 활용	경로 탐색, 사이클 탐지, 미로 찾기	최단 경로 탐색, 레벨 탐색