[Python] 너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)

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

정의

가까운 노드부터 탐색 즉, 시작한 노드와 연결된 인접 노드들을 모드 방문한 후, 방문한 노드들의 인접노드를 차례로 방문

특징

• 레벨 단위 탐색 : 루트 노드로부터 거리에 따라 레벨을 구분
• 최단 경로 탐색 : 가중치가 동일한 경우 시작 노드로부터 각 노드까지 최단경로 구할 때 유용
• 다음 방문할 노드를 저장하기 위해 큐 자료구조를 사용

활용

• 최단 경로 탐색
  • 시작점 ~ 모든 노드까지 최단경로(간선 수)를 탐색
  • ex) 미로찾기, 네트워크 최단경로
• 레벨 순서 탐색
  • 트리의 각 레벨별 노드를 순서대로 방문하여, 레벨 별 데이터를 처리하거나 출력
  • ex) 조직도
• 연결 요소 탐색
  • 연결된 노드들의 집합(연결요소)를 식별할 때 사용
  • ex) SNS 친구 그룹 찾기

흐름 및 구현 예제

1. 시작 노드를 큐에 삽입, 방문 처리
2. 큐에서 노드를 꺼내, 해당 노드의 인접 노드를 확인
3. 방문하지 않은 인접노드를 큐에 삽입, 방문 처리
4. 2~3 반복

초기 설정

from collections import deque

def bfs(graph, start):
    # graph: 각 노드와 인접한 노드들을 저장한 딕셔너리 (예: {"A": ["B", "C"], ...})
    # start: 시작 노드
    visited = set()       # 방문한 노드를 기록하기 위한 집합
    queue = deque([start])  # 시작 노드를 큐에 삽입

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

탐색 구현

while queue:
    node = queue.popleft()  # 큐에서 노드를 하나 꺼냄
    if node not in visited:
        print(node, end=" ")  # 방문한 노드 출력
        visited.add(node)     # 노드를 방문 처리
        # 현재 노드의 인접 노드들 중 방문하지 않은 노드를 큐에 추가
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)

bfs(graph, "A") # A부터 그래프를 방문 탐색

# 탐색 순서 : A, B, C, D, E, F

실제 단계별 탐색 흐름

[초기] 
Visited: {A}
Queue: [A]

[A 처리] (큐에서 빼냄)
Visited: {A, B, C}      A의 이웃: B, C
Queue: [B, C]

[B 처리] (큐에서 빼냄)
Visited: {A, B, C, D, E}  B의 이웃: D, E (A 무시)
Queue: [C, D, E]

[C 처리] (큐에서 빼냄)
Visited: {A, B, C, D, E, F}  C의 이웃: F (A 무시)
Queue: [D, E, F]

[D 처리] (큐에서 빼냄)
Queue: [E, F]             D의 이웃: B (방문됨)

[E 처리] (큐에서 빼냄)
Queue: [F]                E의 이웃: B, F (모두 방문됨)

[F 처리] (큐에서 빼냄)
Queue: []                 F의 이웃: C, E (모두 방문됨)

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

정의

그래프나 트리의 한 노드에서 시작하여 한 방향으로 깊게 들어간 후, 더이상 진행할 수 없을 경우 마지막 분기점으로 돌아와 다른 경로를 탐색

특징

• 깊이 우선 탐색: 한 경로를 가능한 한 깊게 탐색한 후, 더 이상 진행할 수 없으면 이전 분기점으로 돌아가 다른 경로를 탐색합니다.
• 방문 순서: 경로를 따라 깊게 들어가므로, 한 경로의 끝까지 탐색한 후 되돌아가는 특징이 있습니다.
• 메모리 효율성: 일반적으로 BFS에 비해 메모리 사용량이 적을 수 있음

활용

• 경로 찾기 및 미로 탐색
  • 특정 시작점에서 목적지까지의 경로를 찾거나 미로 문제를 풀 때 사용됩니다.
• 백트래킹 알고리즘:
  • 순열, 조합, N-Queen 문제 등에서 모든 가능한 해를 탐색
• 그래프 구성 요소 찾기:
  • 연결 요소, 강한 연결 요소(SCC)
• 위상 정렬:
  • 방향성 비순환 그래프(DAG)에서 DFS를 사용해 정점 간 순서를 정립
• 사이클 검출:
  • 그래프 내 사이클 여부를 확인하는 알고리즘에 DFS가 사용됩니다.

흐름 및 구현 예제

재귀방식 구현

def dfs_recursive(node, visited=None):
    if visited is None:
        visited = set()  # 방문한 노드를 기록할 집합

    # 노드가 이미 방문되었으면 재귀 호출 종료
    if node in visited:
        return

    # 현재 노드를 방문 처리
    print(node, end=" ")
    visited.add(node)

    # 인접 노드들을 재귀적으로 탐색
    for neighbor in graph.get(node, []):
        dfs_recursive(neighbor, visited)

# 예제 그래프 (인접 리스트로 표현)
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

# DFS 실행 (재귀 방식)
dfs_recursive("A")

반복문 방식(스택)

def dfs_iterative(start):
    visited = set()       # 방문한 노드를 기록
    stack = [start]       # 스택에 시작 노드 삽입

    while stack:
        node = stack.pop()  # 스택의 최상단 노드를 꺼냄
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            # 인접 노드를 스택에 추가 (역순으로 추가하면 원래 순서를 유지 가능)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

# 예제 그래프 (이전과 동일)
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

# DFS 실행 (반복문 방식)
dfs_iterative("A")

실제 단계별 탐색 흐름

[초기]
    •    Visited: {}
    •    Stack: [A]

⸻

[A 처리]
    •    스택에서 A를 꺼내고 방문 → Visited: {A}
    •    A의 인접 노드: [B, C]
    •    DFS에서는 왼쪽(먼저 방문) 노드를 먼저 탐색하기 위해,
스택에 인접 노드들을 역순으로 넣습니다.
    •    reversed([B, C]) → [C, B]
    •    스택: [C, B]

⸻

[B 처리]
    •    스택에서 B를 꺼내고 방문 → Visited: {A, B}
    •    B의 인접 노드: [A, D, E]
    •    A는 이미 방문 → 남은 [D, E]
    •    reversed([D, E]) → [E, D]
    •    스택: [C, E, D]

⸻

[D 처리]
    •    스택에서 D를 꺼내고 방문 → Visited: {A, B, D}
    •    D의 인접 노드: [B]
    •    B는 이미 방문 → 아무것도 추가하지 않음
    •    스택: [C, E]

⸻

[E 처리]
    •    스택에서 E를 꺼내고 방문 → Visited: {A, B, D, E}
    •    E의 인접 노드: [B, F]
    •    B는 이미 방문 → 남은 [F]
    •    reversed([F]) → [F] (그대로 추가)
    •    스택: [C, F]

⸻

[F 처리]
    •    스택에서 F를 꺼내고 방문 → Visited: {A, B, D, E, F}
    •    F의 인접 노드: [C, E]
    •    E는 방문됨, C는 미방문
    •    reversed([C, E]) → [E, C] → E는 무시 → [C] 추가
    •    스택: [C, C]
(중복이 있을 수 있으나, 방문 전에 체크하므로 괜찮습니다.)

⸻

[C 처리]
    •    스택에서 C를 꺼내고 방문 → Visited: {A, B, D, E, F, C}
    •    C의 인접 노드: [A, F]
    •    모두 방문됨
    •    스택: [C]

⸻

[남은 C 처리]
    •    스택에서 남은 C를 꺼내지만, 이미 방문되어 아무 작업도 하지 않음
    •    스택: []

⸻

종료
    •    스택이 비었으므로 탐색 종료

최종 방문 순서: A → B → D → E → F → C