알고리즘 03 - (기본 패턴 02) - (1) 그래프 탐색, BFS (너비 우선 탐색, Breadth-First Search)?

그래프 탐색: BFS (너비 우선 탐색, Breadth-First Search)

---

1. BFS란?

BFS는 그래프 탐색 알고리즘으로, 시작 노드에서 가까운 노드부터 순차적으로 탐색하는 방법입니다.
탐색 과정에서 큐(Queue) 자료구조를 사용하며, 노드를 수평적으로(너비 우선) 탐색합니다.

---

2. BFS 작동 원리

1. 초기화:
   • 시작 노드를 큐에 추가합니다.
   • 방문 상태를 기록하는 데이터 구조(예: 집합 또는 리스트)를 준비합니다.
2. 탐색 반복:
   • 큐에서 노드를 꺼내 방문 상태에 추가합니다.
   • 현재 노드와 연결된 노드 중 아직 방문하지 않은 노드를 큐에 추가합니다.
   • 큐가 빌 때까지 이 과정을 반복합니다.
3. 탐색 종료:
   • 큐가 비면 모든 노드를 탐색한 것이므로 종료합니다.

---

3. BFS의 특징

• 탐색 순서:
  • 시작 노드 → 인접 노드(1단계) → 인접 노드의 인접 노드(2단계).
• 경로의 길이:
  • 모든 경로가 동일한 가중치를 가질 경우, BFS는 최단 경로를 보장합니다.
• 시간 복잡도:
  • ( O(V + E) ): ( V )는 노드 수, ( E )는 간선 수.

---

4. BFS를 기억하기 쉽게 설명

1. “가까운 곳부터 차례대로 방문한다.”
   • 시작점에서 가장 가까운 노드를 먼저 탐색하고, 이후 점차 멀리 있는 노드를 탐색합니다.
2. “큐를 사용한다.”
   • BFS는 “탐색할 노드”를 저장하기 위해 큐를 사용합니다.
   • 큐에서 꺼낸 순서대로 탐색합니다.

---

5. BFS 구현 예제: 과정을 출력

그래프

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

코드

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문 상태
    queue = deque([start])  # 탐색할 노드를 저장할 큐

    print(f"그래프 구조: {graph}")
    print(f"시작 노드: {start}")
    print("========================================")

    step = 1
    while queue:
        print(f"Step {step}:")
        print(f" - 현재 큐 상태: {list(queue)}")

        # 큐에서 노드를 꺼냄
        node = queue.popleft()
        print(f" - 큐에서 꺼낸 노드: {node}")

        # 방문하지 않은 경우 처리
        if node not in visited:
            visited.add(node)
            print(f" - 방문한 노드: {node}")
            print(f" - 방문 상태: {visited}")

            # 인접 노드 중 방문하지 않은 노드를 큐에 추가
            next_nodes = [n for n in graph[node] if n not in visited]
            queue.extend(next_nodes)
            print(f" - 추가된 노드들: {next_nodes}")
        else:
            print(f" - 노드 {node}는 이미 방문됨")

        print(f" - 큐 상태 갱신: {list(queue)}")
        print("----------------------------------------")
        step += 1

    print("탐색 완료!")
    print(f"방문한 노드 순서: {visited}")

출력

bfs(graph, 1)

출력 결과:

그래프 구조: {1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [], 6: [], 7: []}
시작 노드: 1
========================================
Step 1:
 - 현재 큐 상태: [1]
 - 큐에서 꺼낸 노드: 1
 - 방문한 노드: 1
 - 방문 상태: {1}
 - 추가된 노드들: [2, 3]
 - 큐 상태 갱신: [2, 3]
----------------------------------------
Step 2:
 - 현재 큐 상태: [2, 3]
 - 큐에서 꺼낸 노드: 2
 - 방문한 노드: 2
 - 방문 상태: {1, 2}
 - 추가된 노드들: [4, 5]
 - 큐 상태 갱신: [3, 4, 5]
----------------------------------------
Step 3:
 - 현재 큐 상태: [3, 4, 5]
 - 큐에서 꺼낸 노드: 3
 - 방문한 노드: 3
 - 방문 상태: {1, 2, 3}
 - 추가된 노드들: [6, 7]
 - 큐 상태 갱신: [4, 5, 6, 7]
----------------------------------------
Step 4:
 - 현재 큐 상태: [4, 5, 6, 7]
 - 큐에서 꺼낸 노드: 4
 - 방문한 노드: 4
 - 방문 상태: {1, 2, 3, 4}
 - 추가된 노드들: []
 - 큐 상태 갱신: [5, 6, 7]
----------------------------------------
Step 5:
 - 현재 큐 상태: [5, 6, 7]
 - 큐에서 꺼낸 노드: 5
 - 방문한 노드: 5
 - 방문 상태: {1, 2, 3, 4, 5}
 - 추가된 노드들: []
 - 큐 상태 갱신: [6, 7]
----------------------------------------
Step 6:
 - 현재 큐 상태: [6, 7]
 - 큐에서 꺼낸 노드: 6
 - 방문한 노드: 6
 - 방문 상태: {1, 2, 3, 4, 5, 6}
 - 추가된 노드들: []
 - 큐 상태 갱신: [7]
----------------------------------------
Step 7:
 - 현재 큐 상태: [7]
 - 큐에서 꺼낸 노드: 7
 - 방문한 노드: 7
 - 방문 상태: {1, 2, 3, 4, 5, 6, 7}
 - 추가된 노드들: []
 - 큐 상태 갱신: []
----------------------------------------
탐색 완료!
방문한 노드 순서: {1, 2, 3, 4, 5, 6, 7}

---

6. BFS를 스스로 사고하고 암기하기

1. 핵심 아이디어 기억:
   • “가까운 노드부터 차례대로 탐색”.
   • 탐색에 큐(Queue) 사용.
2. 암기법:
   • “큐에 추가 → 꺼내서 방문 → 인접 노드 추가.”
3. 손으로 풀어보기:
   • 작은 그래프를 직접 그려서 큐 상태와 방문 상태를 적어보세요.
4. 반복 연습:
   • 다양한 그래프 구조를 직접 구현해보세요.
   • 예: 사이클 있는 그래프, 비연결 그래프.

---

7. 정리

• BFS는 가까운 노드부터 차례대로 탐색하는 알고리즘.
• 특징:
  • 큐 사용.
  • 최단 경로 보장(모든 간선의 가중치가 동일한 경우).
• 핵심 과정:
  • 큐에서 노드 꺼내기 → 방문 → 인접 노드 추가.
• 암기법:
  • “큐에 추가 → 꺼내서 방문 → 인접 노드 추가.”