[바킹독의 실전 알고리즘] 0x09강 - BFS

 

알고리즘 설명

BFS(Breadth First Search)는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.

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

여기서 그래프는 정점과 간선으로 이루어진 자료구조를 말한다.

 

BFS 과정

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

모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)이다.
만약 행이 R개이고 열이 C개이면 시간 복잡도는 O(RC)이다.

 

구현 시 체크해야 하는 부분

• 시작점에 방문했다는 표시를 남겨야 한다.
• 큐에서 빼낼 때가 아닌, 큐에 넣을 때 방문했다는 표시를 남겨야 한다.
• 이웃한 원소가 범위를 벗어났는지에 대한 체크가 잘 되었는지 확인한다.

 

출처: 바킹독님 블로그