DFS, BFS

DFS, BFS란?

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

• 트리나 그래프를 탐색하는 방법
• 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색
• 끝까지 탐색하면 다시 위로 올라가 다음 노드를 탐색
• 모든 경로를 깊이 먼저 탐색하는 방식

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

• 한 노드를 시작으로 인접한 모든 정점을 우선 방문
• 더 이상 방문하지 않은 정점이 없을 때까지 넓이 우선으로 탐색
• 같은 레벨의 노드를 먼저 탐색하는 방식

---

왜 DFS와 BFS를 배울까?

• 이분 탐색처럼 효율적인 방법도 있지만, 모든 경우의 수를 탐색해야 하는 문제도 존재
• DFS와 BFS는 모든 경우의 수를 탐색하면서도
  • DFS는 깊이 우선으로,
  • BFS는 넓이 우선으로 순서를 달리하여 탐색
• 탐색 순서에 따라 문제 해결 전략이 달라질 수 있음

---

DFS의 특징

• 끝까지 파고드는 방식으로, 그래프의 최대 깊이만큼 공간을 요구
• 상대적으로 공간을 적게 사용
• 최단 경로를 찾기에는 적합하지 않음
• DFS는 재귀 호출이나 스택을 사용하며, 한 번에 탐색 중인 경로만 저장
• 최대 저장 노드 수는 그래프 깊이 d 정도

쉽게 말하면, “한 길을 끝까지 파고 내려가면서 그 길만 기억”하는 느낌

---

BFS의 특징

• 모든 분기되는 노드를 넓이 우선으로 탐색
• 최단 경로를 쉽게 찾을 수 있음
• 모든 분기 노드를 저장해야 하므로 공간을 많이 사용
• 모든 노드를 탐색하므로 시간이 오래 걸릴 수 있음
• BFS는 큐를 사용하며, 현재 레벨에 있는 모든 노드를 동시에 저장
• 최대 저장 노드 수는 가장 넓은 레벨 너비 w 정도

쉽게 말하면, “한 층에 있는 모든 노드를 한꺼번에 기억”하는 느낌

---

DFS와 BFS 공간 비교

탐색 방식	자료구조	최대 저장 노드 수	공간 특징
DFS	스택/재귀	최대 그래프 깊이 d	깊이가 낮으면 공간 적게 사용
BFS	큐	최대 레벨 너비 w	레벨이 넓으면 공간 많이 사용

---

즉, 같은 그래프라도 DFS는 한 경로만, BFS는 한 레벨 전체를 저장하기 때문에 공간 사용 패턴이 다르다.
문제 상황에 맞게 DFS와 BFS를 선택하면 효율적으로 탐색할 수 있다.

---

DFS - 코드로 구현

DFS는 크게 재귀 함수 방식과 스택을 활용한 반복문 방식으로 구현할 수 있습니다.

---

1. 재귀 함수 방식

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        current_node = stack.pop()
        if current_node not in visited:   # 방문 체크 필요
            visited.append(current_node)
            # 인접 노드를 stack에 추가
            for adjacent_node in adjacent_graph[current_node]:
                if adjacent_node not in visited:
                    stack.append(adjacent_node)

    return visited


print(dfs_stack(graph, 1))

✅ 특징

• 코드가 간결하고 이해하기 쉬움
• 하지만 탐색 깊이가 깊어질 경우 RecursionError (재귀 깊이 초과) 발생 가능
• 호출 스택에 함수 실행 정보가 쌓이므로 약간의 메모리 오버헤드가 있음

---

2. 스택을 이용한 반복문 방식

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        current_node = stack.pop()
        visited.append(current_node)

        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)

    return visited


print(dfs_stack(graph, 1))

✅ 특징

• 반복문과 스택 자료구조를 활용 → 재귀 깊이 제한 없음
• 필요한 데이터만 저장하므로, 재귀보다 메모리 효율적
• 코드가 조금 더 길지만, 큰 그래프 탐색에서 안정적

📌 DFS 구현 방식 비교

방식	장점	단점
재귀 DFS	코드가 간단하고 직관적	깊이 제한 존재 → RecursionError 발생 가능
스택 DFS	깊이 제한 없음, 메모리 효율적	코드가 재귀보다 조금 길어짐

---

BFS - 코드로 구현

BFS(Breadth-First Search)는 한 레벨씩 너비 우선으로 탐색하는 방법입니다.
보통 큐(Queue) 자료구조를 이용해서 구현합니다.

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = deque()
    visited = []
    queue.append(start_node)

    while queue:
        current_node = queue.popleft()

        for adj_node in adj_graph[current_node]:
            if adj_node not in visited:
                visited.append(adj_node)
                queue.append(adj_node)

    return visited


print(bfs_queue(graph, 1))

✅ 특징

• 큐를 이용해 한 레벨씩 탐색 → 너비 우선
• 노드를 큐에 넣을 때 방문 처리 → 중복 방문 방지
• 사이클이 있는 그래프에서도 안전하게 동작
• 최단 경로 탐색에 유리

📌 요약

• BFS는 한 레벨씩 탐색하므로, 그래프 레벨 구조를 활용한 문제에 적합
• DFS와 다르게 끝까지 파고드는 깊이 우선이 아니라, 같은 레벨 노드들을 먼저 방문
• 큐에 노드를 넣을 때 바로 방문 처리하면 중복 방문 방지와 효율적인 탐색 가능