너비 우선 탐색 (BFS) 이란?

BFS는 Breadth First Search, 너비 우선 탐색이라고 부르며 코딩 테스트에서 자주 등장하는 알고리즘 중에 하나다.

기본적으로 그래프 탐색에 사용되며, 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

<aside> 💡

Tip. BFS로 얻게 된 노드들의 탐색 경로는 해당 노드로 도달할 수 있는 최단거리이다.

</aside>

Untitled

Untitled

BFS는 큐(Queue) 자료구조를 사용해서 구현할 수 있다.

너비 우선 탐색 과정

Java Code

Java 코드로 구현하는데 필요한 것들은 다음과 같다.

  1. boolean[] visited
  2. 인접 행렬 or 인접 리스트

LinkedList를 사용한 BFS 구현