Depth First Search (DFS)
다차원 배열에서 각 칸을 방문(순회)할 때 깊이를 우선으로 방문하는 알고리즘이다. 반면 BFS는 너비 우선 방문 알고리즘이다.
- 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.
- 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다.
- 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다.
- 스택이 빌 때까지 2번을 반복한다.
모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.
DFS / BFS 차이점
DFS도 BFS처럼 Flood Fill 기능이 필요할 때 사용할 수 있다. BFS와 최종적인 방문 결과는 똑같지만, 방문 순서에 차이가 존재한다.
BFS의 경우 거리 순으로 넓게 방문한다는 성질이 존재하지만, DFS의 경우 막다른 곳에 다다를 때까지 한 방향으로 깊게 방문하는 모습을 확인할 수 있다.
BFS에는 또한 '현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다'는 성질이 존재하지만, DFS에서는 성립하지 않는다.
결과적으로, Flood Fill 기능을 구현하는 데에 있어 BFS와 DFS 중 어느것을 써도 무방하지만 거리 측정에는 BFS만을 쓸 수 있다.
DFS는 그래프와 트리 자료구조를 다룰 때 유용하게 쓰인다.