[바킹독의 실전 알고리즘] 0x0A강 - DFS

DFS

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

DFS는 별거 없이 BFS를 사용할 때 사용했던 큐가 스택으로 바뀐 것 뿐

BFS는 너비우선이고 DFS는 깊이우선이다.

그래서 BFS는 경로를 큐에 담으면서 여러 경로를 한번에 추적한다

DFS는 한 경로를 쭉 먼저 탐색 후, 다음 경로도 쭉 탐색한다 한곳만 파는거다

예시

이미지에서 보여준 것과 같이 스택에 쌓이면 top에 있는 경로를 가지고 다시 방문을 시작하는것을 반복한다.

BFS vs DFS

처음 설명한 것 처럼 BFS는 퍼져나가는식, DFS는 상하좌우에서 한 쪽만 먼저 쭉 탐색 후 남은 경로로 또 다시 쭉 탐색한다.

이렇게 방문 순서에 큰 차이가 있다.

DFS는 BFS의 특징인 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다." 가 성립 하지 않는다. 그래서 다차원 배열을 순회하는 문제에서는 BFS로만 짜도 된다. 그렇다고 해서 DFS가 쓸모가 없는게 아니다. 자료구조의 그래프와 트리에서 사용하게되니 특징만 잘 알고 넘어가면 될 듯