[Algorithm] 4-(4) BFS(Breadth-First Search)

[Algorithm] 4-(4) BFS(Breadth-First Search)

 

 

너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용한다.

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 (2)번 과정을 수행할 수 없을 때 까지 반복한다.

 

최단 거리 목적을 달성하기 위한 알고리즘으로 사용되기도 한다.

 

 

대표 문제

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS