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

개요

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

예제

• graph
  • 
• C++

  • 코드

    #include #include 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