너비 우선 탐색 (BFS, Breadth First Search) 한 노드에서 시작한 후 시작 노드의 인접한 노드부터 탐색하는 방법이다. 가까운 노드부터 탐색하는 알고리즘 이다. 시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 있는 노드는 마지막에 방문하는 방식이다. 넓게 탐색하는 방식이다. 일반적으로 선입선출 방식인 큐 자료구조를 활용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색이 이루어진다. 특징 여러 갈래중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우에는 DFS는 무한루프에 빠져 종료되지 못하지만, BFS는 동시에 탐색이 진행되기때문에 탐색이 완료될 수 있다. 모든길을 한번씩 탐색하기 때문에..