BFS(Breadth First Search)

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

위의 그림에 '그래프' 라는 자료구조의 완전 탐색을 위한 알고리즘.

DFS와 마찬가지로 방문배열과 인접 리스트로 표현하지만, 선입선출 구조를 사용해야하기 때문에, Queue 자료구조를 사용합니다.

• 그래프 : 정점(Node)과 간선(Edge)으로 이뤄진 자료구조

알고리즘 과정

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

방문 표시를 통해 한번 방문한 곳에는 방문하지 않으므로, 모든 칸이 큐에 1번씩 들어가게 됩니다. 따라서, 시간 복잡도는 칸이 N개 일 때, O(N)입니다.