탐색-BFS

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.
DFS , BFS , 이진탐색이 있다.

이론

📖 BFS (너비우선탐색)

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

• 선입선출방식으로 탐색하므로 큐를 이용하여 문제를 푼다.
• 위의 <그림> 에서 탐색순서는 1->2->3->5->6->4 가 된다.

문제풀이

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준