BFS - algorithm[3]

BFS(Breadth First Search)

BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다.

Example

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김

2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입

4. 큐가 빌 때까지 2번을 반복

잘못 구현한 경우

1. 시작점에 방문했다는 표시를 남기지 않는다.

2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 표시를 남겼다.

3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

큐에서 빼낼 때 방문했다는 표시를 남기게 되면 같은 위치가 큐에 여러 번 들어가게 된다.