BFS (Breadth First Search)

BFS란?

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

BFS 방문 절차

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내고, 해당 칸에 상하좌우 인접 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 해당 칸을 큐에 넣고 방문했다는 표시를 남김
4. 큐가 빌때까지 2번을 반복

BFS의 특징

1. 모든 칸이 큐에 1번씩만 들어가므로 O(N)

BFS 구현

주의사항

1. 시작점에 방문 표시를 하지 않음 (> 시작점을 두 번 방문할 수 있음)
2. 큐에 넣을 때 방문 표시를 남기지 않고, 큐에서 뺄 때 방문표시를 남김 (> 같은 칸이 큐에 여러번 들어갈 수 있음)
3. 이웃 원소의 범위 체크를 하지 않음 (> 범위에 벗어난 칸을 체크하게 될 수 있음)