DFS (Depth First Search)

DFS란?

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

DFS 방문 절차

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

DFS의 특징

1. 모든 칸이 스택에 1번씩만 들어가므로 O(N)

BFS vs. DFS

방문 순서에 큰 차이가 있다. 단, BFS의 경우 거리를 측정할 수 있다는 점에서, Flood Fill 문제 접근 시엔 DFS 보다는 BFS를 사용하는 것이 좋다.
하지만 그래프, 트리 자료구조에서 DFS가 필요하므로 개념은 알고있어야 함.