BFS - 너비 우선 탐색

✏️ BFS 란?

📍 기본 이론

• 그래프를 완전탐색하는 방법 중 하나로,
  시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
  - 목표노드의 끝에 도착하는 경로가 여러개일 때 최단 경로를 보장한다.
• DFS 와 반대로 FIFO 방식인 Queue 가 사용된다.

📍 핵심이론

1. BFS 를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기

1. 원본 그래프를 인접 리스트로 표현한다.
2. 반문 배열을 초기화 한다.
3. 탐색을 위해 시작노드를 Queue 에 삽입 하고, 방문 배열에 기록한다.
   • 3번을 제외한 1,2 번은 DFS 와 동일하다.

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

1. Queue 에서 노드를 꺼내면서 탐색 순서에 노드를 기입한다.
2. Queue 에서 꺼낸 노드의 인접 노드를 Queue 에 삽입하고, 방문 배열에 기록한다.

3. 1번 2번 반복하기

• Queue 에 값이 없을 때 까지 반복한다.
  • 이 때 이미 다녀간 노드는 방문 배열을 참고해 다시 삽입되지 않도록 한다.