[탐색] BFS (너비 우선 탐색)

✔ 너비 우선 탐색

너비 우선 탐색이란?

• 그래프 완전 탐색 기법 중 하나
• 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
• 큐 자료구조를 이용하여 구현이 가능 (FIFO)
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E)
• 목표 노드에 도착하는 경로가 여러 개일때의 최단 경로를 보장할 때 사용 

너비 우선 탐색 과정

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   • 인접 리스트로 그래프 표현하기
   • 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 방문 배열 초기화하기
   • 시작 노드 큐에 삽입하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
   • poll을 수행하여 노드 꺼내기
   • 꺼낸 노드를 탐색 순서에 기입하기
   • 꺼낸 노드의 인접 리스트의 인접 노드를 삽입하여 방문 배열 체크하기
3. 큐 자료구조에 값이 없을 때까지 반복하기
   • 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn