BFS(너비 우선 탐색)

1. BFS (Breadth-First Search)

• BFS는 그래프나 트리의 모든 노드를 넓게 탐색하는 알고리즘
• 작동 원리: 시작 노드를 큐에 넣고, 큐에서 하나씩 꺼내면서 그 노드와 연결된 모든 노드를 큐에 추가하는 방식으로 탐색
• BFS 알고리즘은 큐 자료구조에 기초하기 때문에 deque 라이브러리를 활용하여 구현
• 시간 복잡도는 O(N) 의 시간이 소요
• 일반적인 경우에 실제 수행 시간은 DFS 보다 BFS가 좋은 편

2. BFS 활용 예시

1) 최단 경로 찾기: BFS는 가중치가 동일한 그래프에서 최단 경로를 찾을 때 유용하다.
2) 네트워크 탐색: 컴퓨터 네트워크에서 연결 상태를 확인하거나, SNS에서 친구 추천 기능 등을 구현할 때 사용할 수 있다.

3. BFS 기본 알고리즘 (그래프에서)

1) 시작 노드를 큐에 넣고 방문 처리

2) 큐에서 노드를 하나씩 꺼내면서, 그 노드와 연결된 인접 노드들을 큐에 넣고 방문 처리

3) 큐가 비어 있을 때까지 반복

노드의 탐색 순서, 즉 큐에 삽입한 순서
=> 1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7

4. BFS 코드 구현 (파이썬 예시)

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)  # 방문 여부 체크 리스트
    queue = deque([start])  # 시작 노드를 큐에 넣음
    visited[start] = True  # 시작 노드는 방문 처리

    while queue:
        node = queue.popleft()  # 큐에서 노드 꺼내기
        print(node, end=" ")  # 현재 노드 출력

        # 현재 노드와 연결된 모든 인접 노드들 큐에 넣기
        for neighbor in graph[node]:
            if not visited[neighbor]:  # 방문하지 않은 노드만
                queue.append(neighbor)
                visited[neighbor] = True  # 방문 처리

# 그래프 (인접 리스트 형태)
graph = [
    [1, 2],  # 노드 0과 연결된 노드들
    [0, 3, 4],  # 노드 1과 연결된 노드들
    [0, 4],  # 노드 2와 연결된 노드들
    [1],  # 노드 3과 연결된 노드들
    [1, 2]  # 노드 4와 연결된 노드들
]

bfs(graph, 0)

5. 연습문제

1260 - DFS와 BFS
2178 - 미로 탐색
7576 - 토마토
1697 - 숨바꼭질