너비 우선 탐색(BFS, Breadth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 노드에서부터 시작하여 한 단계씩 가능한 한 넓은 범위의 노드를 탐색하는 방식입니다. 즉, 같은 레벨에 있는 노드들을 먼저 탐색한 후에 다음 레벨로 넘어가는 방식입니다. 큐(Queue) 자료구조를 사용하여 구현합니다.

BFS의 주요 특징은 다음과 같습니다:

1. 넓게 탐색: 현재 노드와 인접한 노드들을 먼저 탐색하며, 한 레벨씩 넓게 탐색합니다. 이를 통해 시작 노드로부터의 최단 경로를 찾을 수 있습니다.
2. 큐 사용: 큐 자료구조를 사용하여 먼저 들어온 노드를 먼저 탐색하고, 해당 노드와 연결된 노드들을 큐에 넣습니다.
3. 방문 표시: 각 노드를 방문한 노드인지 여부를 표시해야 합니다. 이를 통해 무한 루프를 피하며 모든 노드를 정확히 한 번씩 방문할 수 있습니다.

BFS의 구체적인 작동 방식은 다음과 같습니다:

1. 시작 노드를 선택하고, 해당 노드를 큐에 넣고 방문했다고 표시합니다.
2. 큐에서 하나의 노드를 꺼내 해당 노드의 인접한 노드들을 모두 큐에 넣고 방문했다고 표시합니다.
3. 큐가 빌 때까지 2단계를 반복합니다.

BFS의 활용 예시:

• 최단 경로 찾기: 그래프 내에서 두 노드 간의 최단 경로를 찾을 때 사용됩니다.
• 네트워크 플로우: 그래프에서 최대 플로우를 찾을 때, 간선의 용량을 이동시키는 문제에서 사용됩니다.
• 미로 찾기: 2차원 그리드로 표현된 미로에서 최단 경로를 찾을 때 사용됩니다.

BFS는 재귀 호출을 사용하지 않으므로 스택 오버플로우와 같은 문제가 발생하지 않습니다. 따라서 BFS는 일반적으로 재귀 없이 구현되며, 큐를 사용하여 노드의 탐색 순서를 관리합니다.

아래는 BFS를 파이썬으로 구현한 예시 코드입니다.

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 저장하는 집합
    queue = deque([start])  # 큐를 생성하고 시작 노드를 넣음

    while queue:
        node = queue.popleft()  # 큐의 가장 왼쪽 노드를 꺼냄
        if node not in visited:
            print(node, end=" ")  # 현재 노드 방문
            visited.add(node)  # 방문 표시

            # 현재 노드의 인접한 노드들을 큐에 넣음
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 무방향 그래프 정의 (딕셔너리로 표현)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2, 7],
    6: [3],
    7: [5]
}

# 시작 노드에서부터 BFS 탐색 시작
start_node = 1
bfs(graph, start_node)

이 코드는 무방향 그래프에서 시작 노드로부터 BFS 탐색을 수행하며, 각 노드를 방문하는 순서를 출력합니다. 'graph' 딕셔너리에 노드와 인접 노드 정보를 표현하고, 큐를 사용하여 노드의 탐색 순서를 관리합니다.