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

🔹 BFS란?

1. 너비 우선 탐색(BFS)의 정의

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색 알고리즘으로, 시작 노드에서 가까운 노드부터 탐색하며 점진적으로 멀리 있는 노드를 방문하는 방식입니다. BFS는 큐(Queue)를 활용하여 구현되며, 최단 경로 탐색, 네트워크 분석, 인공지능 경로 탐색 등에 널리 활용됩니다.

✅ BFS의 주요 특징:

• 가장 가까운 노드부터 탐색하는 방식
• 큐(Queue)를 사용하여 구현
• O(V+E)의 시간 복잡도를 가짐 (V: 정점 수, E: 간선 수)
• 최단 경로를 찾는 문제에서 유리함 (비가중 그래프에서 최적해 보장)

📌 BFS는 최단 경로, 네트워크 분석, 웹 크롤링 등에 널리 활용됩니다.

---

🔹 BFS의 구현 방법

1. 큐(Queue) 기반 BFS

✅ 명시적인 큐 자료구조를 사용하여 BFS를 구현하는 방식

✔️ BFS 예제 (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            queue.extend(graph[node])

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
bfs(graph, 'A')  # 출력: A B C D E F

📌 큐를 활용하면 BFS를 효율적으로 구현할 수 있습니다.

---

🔹 BFS vs DFS 비교

비교 항목	너비 우선 탐색(BFS)	깊이 우선 탐색(DFS)
탐색 방식	가장 가까운 노드부터 탐색	한 경로를 끝까지 탐색 후 백트래킹
구현 방식	큐(Queue) 사용	스택(Stack) 또는 재귀(Recursion) 사용
최단 경로	최단 경로 보장 (비가중 그래프)	보장되지 않음
시간 복잡도	O(V+E)	O(V+E)
공간 복잡도	O(V) (큐 크기에 따라 증가)	O(V) (재귀 깊이에 따라 증가)

📌 BFS는 최단 경로 탐색에 적합하며, DFS는 백트래킹 문제에 적합합니다.

---

🔹 BFS의 활용 사례

1. 최단 경로 탐색(Shortest Path Finding)

✅ 비가중 그래프에서 최단 경로를 찾을 때 활용

✔️ 최단 경로 탐색 예제 (Python):

def bfs_shortest_path(graph, start, goal):
    queue = deque([[start]])
    visited = set()
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        elif node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                new_path = list(path)
                new_path.append(neighbor)
                queue.append(new_path)
    return None

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs_shortest_path(graph, 'A', 'F'))  # 출력: ['A', 'C', 'F']

📌 BFS는 최단 경로를 보장하는 탐색 방법이므로, 경로 탐색 문제에서 효과적입니다.

2. 네트워크 및 웹 크롤링(Network & Web Crawling)

✅ 웹 크롤링, 네트워크 패킷 분석 등에 활용

✔️ 웹 크롤링 예제:

def web_crawl(start_page, max_depth):
    queue = deque([(start_page, 0)])
    visited = set()
    while queue:
        page, depth = queue.popleft()
        if depth > max_depth:
            break
        print(f"Crawling: {page}")
        visited.add(page)
        for link in get_links(page):  # 가상의 함수
            if link not in visited:
                queue.append((link, depth + 1))

📌 웹 크롤링에서는 BFS를 사용하여 특정 깊이까지 탐색할 수 있습니다.

3. 퍼즐 문제 해결(Maze Solving)

✅ 미로 찾기 문제에서 최단 경로 탐색에 사용

✔️ 미로 문제 해결 예제:

def solve_maze(maze, start, end):
    queue = deque([(start, [start])])
    while queue:
        (x, y), path = queue.popleft()
        if (x, y) == end:
            return path
        for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
            next_pos = (x+dx, y+dy)
            if next_pos in maze and next_pos not in path:
                queue.append((next_pos, path + [next_pos]))
    return None

maze = {(0,0), (0,1), (1,1), (2,1), (2,2), (3,2)}
print(solve_maze(maze, (0,0), (3,2)))  # 출력: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2)]

📌 BFS를 활용하면 미로에서 최단 경로를 찾을 수 있습니다.

---

📌 결론

✅ 너비 우선 탐색(BFS)은 그래프 탐색에서 가장 많이 사용되는 알고리즘 중 하나입니다.
✅ 큐(Queue)를 사용하여 구현되며, 최단 경로 탐색 문제에서 유리합니다.
✅ BFS는 웹 크롤링, 네트워크 분석, 퍼즐 해결 등 다양한 문제에서 활용됩니다.
✅ DFS와 비교하여 특정한 문제(최단 경로 탐색, 네트워크 분석)에 적합한 선택지가 됩니다.