파이썬으로 BFS 구하기

BFS란?

너비 우선 탐색(Breadth First Search, BFS)은 그래프 탐색 알고리즘의 하나로, 시작 노드에서 인접한 노드들을 먼저 탐색한 다음, 그 다음 단계의 노드들을 탐색하는 방식입니다.
BFS는 주로 최단 경로를 찾거나, 레벨 순서대로 노드를 방문할 때 유용합니다.

BFS의 활용 예

1. 최단 경로 찾기: 그래프에서 두 노드 간의 최단 경로를 찾는 데 유용합니다.
2. 레벨 순서 탐색: 트리 구조의 데이터를 레벨 순서로 탐색할 때 사용됩니다.
3. 미로 찾기: 2차원 배열로 표현된 미로에서 출구를 찾는 데 유용합니다.

BFS 코드 구현 방법

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

탐색 과정

1. 큐에서 노드를 꺼내고, 방문하지 않은 경우 출력합니다.
2. 현재 노드의 이웃 노드를 큐에 추가합니다. 이 때, 이미 방문한 노드는 추가하지 않습니다.