[알고리즘] BFS

너비 우선 탐색이란? (BFS, Breadth First Search)

• 시작 노드에서부터 인접한 노드를 먼저 탐색하며 넓히는 방법
• 핵심 자료구조 : 큐 (Queue)
• deque 라이브러리를 사용하는 것이 좋다

동작 과정

1. 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 인접 노드 중에서 방문하지 않은 모든 노드를 큐에 삽입 후 방문 처리
3. 2번의 과정을 안될때까지 반복

구현

from collections import deque

def bfs(start_node):
    # 1. 큐 생성 및 시작점 넣기
    queue = deque([start_node])
    visited = {start_node} # 방문 기록 (중복 방지)

    # 2. 큐가 빌 때까지 반복
    while queue:
        # 3. 큐에서 하나 꺼내기 (맨 앞)
        current = queue.popleft() 
        print(current) # 방문 처리

        # 4. 현재 노드의 '인접한' 노드들을 확인
        for neighbor in get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor) # 큐에 넣기