링크

동빈나(유투브) - BFS

BFS

너비 우선 탐색(Breadth First Search, BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다. 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법이다. 너비 우선 탐색은 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 준비물은 큐(Queue>이다.

BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 또한 시작 노드를 방문 했을 때 '방문 처리'를 한다. 예를 들면
booelan visited[1(start Node)]=true라고 한다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 Queue에 방문하고 삽입한다.

먼저 시작 노드1을 큐에서 꺼낸다. 그 이유는 Queue는 선입선출(FIFO, First in, First out)이기 때문이다. 이렇게 처리 된 노드1은 가장 위에 두고 주변 노드인 2와 3이 방문된 적이 없으므로 큐에 넣어준다.

큐에서 2를 꺼낸 직후에는 그 인접한 노드 3,4,5 중에서 1과 3은 이미 방문한 적이 있으므로 넘어가고 4와 5를 큐에 삽입한다.

이후에 노드 3을 큐에서 꺼낸 뒤에 인접한 노드인 6과 7을 삽입한다. 노드 1과 2는 방문한적이 있으므로 6과 7만 큐에 넣어주면 된다.

결과는
1-2-3-4-5-6-7
이 된다.