DFS(깊이우선 탐색)

그래프 탐색

하나의 노드으로부터 모든 노드들을 한 번씩 방문하는 것

DFS(Depth-First Search)

시작노드에서 끝까지 내려가면서 탐색하는 방법(깊이를 우선시)
주로 반복문/재귀문 사용

탐색 과정

1. 현재 노드를 방문한 것으로 표시
2. 방문한 표시가 없는 인접 노드들을 탐색
3. 다 방문한 표시가 있으면 역추적(backtracking)함
4. 모든 노드들을 방문할 때까지 위 과정 반복
   
   방문순서
   A -> B -> D -> E -> H -> I -> C -> F -> G -> J

장단점

장점
1. 스택을 사용하기 때문에 메모리 공간을 적게 차지
2. 특정 정점에 빨리 도달하는 것이 목표일 때 유용
3. 순환이 있는지 없는지 감지 가능

단점
1. 순환 그래프일 경우 무한 루프에 빠질 수 있음
2. 최단 경로를 찾는 것이 목표일 경우 가장 좋은 알고리즘이 아닐 수 있음

구현

1. 탐색 시작 노드를 스택에 넣고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs_iterative(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    stack<int> stack;
    vector<int> visitedOrder; // 방문한 노드를 저장하는 배열
    
    stack.push(start);
    
    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();
        
        if (!visited[node]) {
            visited[node] = true;
            visitedOrder.push_back(node); // 방문한 노드를 저장
            
            // graph[node]에 연결된 모든 노드를 순회
            for (int adj : graph[node]) {
                if (!visited[adj]) {
                    stack.push(adj);
                }
            }
        }
    }
    
    // 방문한 노드 출력
    cout << "방문한 노드 순서: ";
    for (int node : visitedOrder) {
        cout << node << " ";
    }
    cout << endl;
}

int main() {
    // 예시 그래프
    vector<vector<int>> graph = {
        {1, 2}, // 0과 연결된 노드
        {3, 4}, // 1과 연결된 노드
        {5, 6}, // 2와 연결된 노드
        {7},    // 3과 연결된 노드
        {},     // 4와 연결된 노드
        {},     // 5와 연결된 노드
        {8, 9}, // 6과 연결된 노드
        {},     // 7과 연결된 노드
        {10},   // 8과 연결된 노드
        {},     // 9와 연결된 노드
        {}      // 10과 연결된 노드
    };
    
    dfs_iterative(graph, 0); // 0번 노드부터 DFS 시작
    
    return 0;
}

관련 문제

문제1

참고자료

자료1
자료2