[WEEK03] DFS와 BFS

🔍 DFS (깊이 우선 탐색)

DFS는 가능한 깊숙이 탐색한 뒤, 더 이상 탐색할 노드가 없으면 다시 돌아와서 다른 경로를 탐색하는 방식이다.

• 구현 방법: 재귀 or 스택
• 장점: 경로 추적, 백트래킹에 유리
• 단점: 최단거리를 보장하지 않음

동작 흐름

1. 현재 노드를 방문 처리
2. 연결된 노드 중 방문하지 않은 노드로 재귀적으로 탐색

🔍 BFS (너비 우선 탐색)

BFS는 시작 노드에서 가까운 노드부터 차례대로 넓게 탐색하는 방법이다.

• 구현 방법: 큐
• 장점: 최단 거리 탐색에 유리
• 단점: 큐에 많은 노드가 쌓이면 메모리 사용량 증가

동작 흐름

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내어 연결된 모든 노드를 큐에 추가

---

💻 코드 구현

✅ 예시 그래프

Graph:
1 - 2 - 5
|   |
3 - 4

graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 4],
    4: [2, 3],
    5: [2]
}

⭐️ DFS 구현 (재귀 방식)

def dfs(graph, v, visited):
    visited.add(v)
    print(v, end=' ')
    for neighbor in graph[v]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 실행
visited = set()
print("DFS 탐색 순서:")
dfs(graph, 1, visited)

DFS 탐색 순서:
1 2 4 3 5

⭐️ BFS 구현 (큐 사용)

from collections import deque

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

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

# 실행
print("BFS 탐색 순서:")
bfs(graph, 1)

BFS 탐색 순서:
1 2 3 4 5

---

🚀 정리

BFS에서 deque를 사용하는 게 시간 효율상 정말 중요하다는 것도 알게 되었다. 추후에 최단거리 문제가 나오면 BFS부터 떠올리자!