너비 우선 탐색

너비 우선 탐색(BFS, breadth-first search)

• 그래프를 완전 탐색하는 방법 중 하나
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
• 선입선출 방식으로 탐색하므로 큐를 이용해 구현
• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

너비 우선 탐색의 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

• 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체그하기 위한 리스트 필요
• 그래프를 인접 리스트로 표현
• 탐색을 위해 큐를 사용

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

• 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입
• 방문 리스트를 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
• 큐에서 꺼낸 노드는 탐색 순서에 기록

3. 큐 자료구조에 값이 없을 때까지 반복하기

• 큐에 노드가 없을 때까지 앞선 과정 반복
• 선입선출 방식으로 탐색