Breadth-First Search

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

1. BFS (너비 우선 탐색)? BFS(Breadth-First-Search)는 너비 우선 탐색으로 큐(FIFO:선입선출)를 통해서 주로 구현이 됩니다. 출발 노드에서 가까운 것부터 접근하는 방식으로, 넓게, 층층히 탐색한다고 생각할 수 있습니다. 최단경로, 임의경로를 탐색해야하는 문제에서 주로 사용됩니다. DFS와 마찬가지로 방문체크를 해줄 필요가 있으며, 방문 체크를 하지 않을 경우 무한루프에 빠질 수 있습니다. 2. 기본적인 원리 기본적인 동작 원리는 다음과 같습니다. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드) pop -> 새 노드 새 노드에 대해 1번 반복 큐에 원소가 없을 때까지 1~3 반복 처음에 시작노..