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

 

알고리즘 설명

DFS(Depth First Search)

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

 

알고리즘 수행 과정

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

모든 칸이 스택에 한 번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.

 

이전 BFS의 수행 과정과 비교해보았을 때, DFS는 스택을 쓴다는 차이만 존재한다.

큐를 쓰면 BFS이고, 스택을 쓰면 DFS가 된다.

 

DFS와 BFS는 노드의 방문 순서에도 차이가 있다.

BFS는 거리 순으로 노드를 방문한다.

DFS는 한 방향으로 더 이상 탐색하는 게 막힐 때까지 직진하며 노드를 방문한다.

 

현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져 있다, 라는 BFS의 성질이 DFS에서는 성립하지 않는다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없다.

 

이후 그래프와 트리라는 자료구조를 배울 때 DFS가 필요하게 된다.

 

 

출처: 바킹독님 블로그