[알고리즘] DFS (Depth-First-Search)

1. DFS란?

DFS란 Depth-First-Search의 줄임말로, 한국어로는 깊이 우선 탐색이라고 한다. DFS에 대해 알기 위해서는 먼저 그래프 탐색에 대해 알아야 하는데, 해당 내용은 이전 글인 BFS에서 언급하였으니 이 링크를 참고하도록 하자.

결론적으로 DFS란 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 막다른 벽을 만나면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 것이다. 즉, 넓게 탐색하기 전에 깊게 탐색하는 방법으로 깊이 우선 탐색이라 일컫는다.

2. DFS의 특징

• 얻어진 해가 최단 경로가 된다는 보장이 없다.
  • 목표 경로가 여러 개인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리기 때문에 이때 얻어진 해가 최적의 해가 아닐 수 있다.
• 현 경로 상의 노드만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다. 하지만 검색 속도 자체는 BFS에 비해서 느리다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가진다.
  • 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 무한루프에 빠질 위험이 있기 때문이다.

3. DFS의 구현 과정

1) 그래프에서의 DFS

1. 시작 노드에 방문한다.
   • 방문한 노드를 표시한다.
2. 시작 노드와 인접한 노드들을 차례로 순회한다.
   • 인접한 노드가 없다면 종료한다.
3. 시작 노드와 인접한 노드 V를 방문했다면, 시작 노드와 인접한 또 다른 노드들을 방문하기 전에 V의 이웃 노드들을 전부 방문해야 한다.
   • V를 시작 노드로 DFS를 다시 시작하여 V의 이웃 노드들을 방문한다.
4. V의 분기를 전부 탐색했다면 다시 시작 노드와 인접한 또 다른 노드 중에서 아직 방문이 되지 않은 노드를 찾는다.
   • 아직 방문이 안된 노드가 없다면 종료한다.
   • 방문이 안된 노드가 있다면 그 노드를 시작 노드로 DFS를 시작한다.

2) 다차원 배열에서의 DFS

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.
2. 스택의 top을 확인하고 해당 칸의 상하좌우로 인접한 칸에 대해 3번 과정을 실행한다.
3. 해당 칸을 이전에 방문한 적이 있으면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남긴 뒤 해당 칸을 스택에 push한다.
4. 스택에 아무것도 남지 않을 때까지 2-3번 과정을 반복한다.