[BOJ/Baekjoon] 16236번:아기상어_python_brushup

BFS (Breadth-First Search)_너비우선검색

1. 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방식으로
2. 시작 정점으로부터 가까운 정점을 먼저 방문하고
   1. 선입선출 방식의 큐(Queue) 자료구조를 활용한다.
      1. 인접한 노드를 반복적으로 큐에 삽입하고
      2. 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘 작성
3. 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법

ex : 미로를 빠져나가는 최단 거리(경로)를 구하는 문제

이걸 구체적인 동작 과정으로 정리하면…

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문처리 한다.
   1. check = [[False]*m for _ in range(n)]
      1. 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크
      2. 탐색한 노드를 재방문하지 않도록 구분하는 것
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문처리한다.
3. 2번의 과정을 더이상 수행할 수 없을때까지 반복한다.
   1. while q: ~
   2. 큐는 선입선출이므로 노드의 레벨 순으로 과정을 수행하게 된다.

• Reference
  https://heytech.tistory.com/56