일단 DFS의 정의는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘입니다. 참고로 BFS는 깊이 대신 너비를 우선으로 방문하는 알고리즘이었습니다.
과정을 먼저 소개해보면 뭔가 어디서 본 것 같다는 느낌을 받을텐데, 바로 BFS의 과정에서 딴건 다 똑같고 큐만 스택으로 바뀐 것 뿐입니다. 큐를 쓰면 BFS이고 스택을 쓰면 DFS가 됩니다. 이번에는 DFS로 상하좌우로 나와 인접한 같은 색의 칸을 방문하는 Flood Fill을 해결해보겠습니다.
이렇게 스택이 비는 순간 과정은 종료됩니다. DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있음을 알 수 있습니다. 그런데 보면서 느끼셨을지 모르겠지만 BFS와 DFS 모두 비록 최종적인 방문 결과는 똑같더라도 방문 순서에서 아주 큰 차이가 있습니다.
이렇게 BFS와 DFS를 살펴보면 BFS는 큐를 쓰고 DFS는 스택을 쓴다는 차이가 있지만 원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 똑같습니다. 하지만 둘의 방문 순서는 큰 차이가 있는데 우선 BFS에서의 방문 순서를 확인해보겠습니다. 시작점을 중앙으로 잡았는데 보면 마치 냇가에 던진 돌로 인해 동심원이 생기는 것 처럼 상하좌우로 퍼져나가는 것을 볼 수 있습니다. 그리고 이전 단원에서 다룬 BFS의 성질인 거리 순으로 방문한다는 것 또한 잘 성립함을 알 수 있습니다. 이번에는 DFS에서의 방문 순서를 확인해보겠습니다. 이건 어떻게 비유를 해야할지 모르겠긴 한데 아무튼 뭔가 차이가 있다는건 알 수 있을 것입니다. 뭔가 한 방향으로 막힐 때 까지 쭉 직진을 한다는걸 알 수 있습니다. 지금 보신 것과 같이 BFS와 DFS는 방문 순서에 큰 차이가 있습니다.
BFS에서 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않습니다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없습니다. Flood Fill은 BFS와 DFS 중에서 어느 것을 써도 상관없는데 거리 측정은 BFS만 할 수 있으니 BFS 대신 DFS를 쓸 일이 없습니다. 그래서 앞으로 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만 짜게 됩니다.