[Algorithm] 19강 : BFS(너비 우선 탐색) 알고리즘 정의와 예제

BFS란? BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 BFS는 큐 자료구조를 이용 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 동작 예시 시작 노드를 1로 정하고 근접한 노드를 찾는다. 이때 방문 기준은 번호가 낮은 인접 노드부터이다. 이때 1에 따라서 2,3,8 이 생긴다. 이걸 큐에 넣고 방문 처리한다. 그다음은 인접했던 값 중에 제일 작았던 2에 대해 인접 노드를 추가해준다. 그전에 있던 1은 사라지고 2와 인접한 노드를 추가해준다. 그래서 3,8,7 이 남는다. 이..