알고리즘 설명

예시

BFS에서 큐를 사용하던 것을 스택으로 바꾸기만 하면 된다.
그렇다면 DFS로 상하좌우로 나와 인접한 같은 색의 칸을 방문하는 Flood Fill을 해결해보자.

큐가 스택으로 대체된 점만 제외하면 여기까지는 BFS와 같다.

이후 top의 원소인 (1,0)이 pop되며, 이 원소를 기준으로 살펴보며 원소 (2,0)을 다시 push한다.
그 이후는 (2,0)을 기준으로 살피게 된다.

DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다.

BFS vs DFS

큐와 스택을 쓴다는 차이를 제외하면 구현은 거의 유사하다. 원소 하나를 빼낸 후 주변을 살펴 방문하지 않은 곳을 찾아 넣는 알고리즘!
하지만 둘의 방문 순서는 큰 차이가 있다. 시작점을 중앙으로 잡았을 때, 우선 BFS에서는 냇가에 돌을 던졌을 때 생기는 동심원처럼 상하좌우로 퍼져나가며 방문하는 것을 알 수 있다. 반면 DFS에서는 한번 진행한 방향에서 더 이상 진행할 수 없을 때까지 계속 직진하는 모습이다.

그리고 BFS에서 유용하게 썼던 "현재 칸으로부터 추가되는 인접한 칸의 거리는 현재 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다.

위 그림은 (0, 0)에서 DFS를 시작할 때 나오는 상황인데, (0,0)에서 빨간색 칸까지의 최단거리가 4인 반면, 검정색 칸까지의 최단 거리는 3이다. 거리를 계산할 때에는 DFS를 사용할 수 없고, 결국 다차원 배열에서 굳이 BFS 대신 DFS를 써야하는 일이 없다고 볼 수 있다.
Flood Fill은 BFS와 DFS 중에서 어느 것을 써도 상관없는데 거리 측정은 BFS만 할 수 있으니, 앞으로 다차원 배열에서 순회에서는 BFS를 이용하자.(DFS는 그래프와 트리에서 사용된다.)