[알고리즘]너비우선탐색(BFS)

너비우선탐색(BFS)란?

루트노드에서 시작해 인접한 노드부터 먼저 탐색하는 방법

BFS의 특징

📔 재귀적으로 동작하지 않는다.
📔 방문한 노드들을 차례로 꺼낼 수 있는 큐(Queue)를 사용한다. 즉, FIFO원칙으로 탐색

BFS 탐색과정

1. 루트노드를 방문한다.
📕 큐에 방문한 노드를 삽입(enqueue)한다.
📕 루트노드의 이웃 노드를 모두 방문한 다음 이웃의 이웃들을 방문한다.
2. 큐에서 꺼낸 노드와 인접한 노드들을 차례로 방문한다.
📘 큐에서 꺼낸 노드들을 방문한다.
📘 큐에서 꺼낸 노드와 이웃한 노드들을 차례로 방문한다.
📘 큐에 방문한 노드들을 삽입(enqueue)한다.