[알고리즘] 깊이 우선 탐색(Depth First Search)

개요

• 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식
• 검색보다 순회에 주로 사용
• 백트래킹에 주로 사용
• 현 경로상의 노드들만 기억하면 되므로 저장공간을 적게 사용
• 해가 여러개일 경우 최단 경로가 아닐 수 있음

예제

• graph
  • 
• C++

  • 코드

       #include <iostream>
       #include <vector>
            
       using namespace std;
            
       void dfs(vector<int> graph[], bool visited[], const int& currentVertex) {
           visited[currentVertex] = true;
            
           cout << currentVertex << "\n";
            
           for (const auto& iter : graph[currentVertex]) {
               if (visited[iter] == false) {
                   dfs(graph, visited, iter);
               }
           }
       }
            
       int main() {
           ios::sync_with_stdio(false);
           cin.tie(nullptr);
           cout.tie(nullptr);
            
           const int maxVertex = 10;
            
           vector<int> graph[maxVertex] = {{1, 2}, {3, 4}, {5, 6}};
            
           bool visited[maxVertex] = {
               false,
           };
            
           dfs(graph, visited, 0);
            
           return 0;
       }
    

  • 결과

    0
    1
    3
    4
    2
    5
    6