[C++로 배우는 알고리즘과 자료구조] Day 23: 깊이 우선 탐색 (DFS)

깊이 우선 탐색 (DFS, Depth-First Search)

깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 가능한 한 깊게 탐색한 후 더 이상 깊이 갈 수 없으면 다시 되돌아와 다른 경로를 탐색하는 방식입니다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 구현이 가능합니다.

DFS의 주요 특징:

• 시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.
• 공간 복잡도: (O(V)), 재귀 호출 스택의 깊이입니다.

DFS 구현

그래프 구현 (인접 리스트 사용)

#include <iostream>
#include <vector>
#include <list>

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w); // 간선 추가
    void DFS(int v); // DFS 호출

private:
    int vertices; // 정점의 수
    std::vector<std::list<int>> adjList; // 인접 리스트
    void DFSUtil(int v, std::vector<bool>& visited); // DFS 유틸리티 함수
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가 함수 정의
void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // 정점 v에 정점 w를 추가
}

// DFS 유틸리티 함수 정의
void Graph::DFSUtil(int v, std::vector<bool>& visited) {
    // 현재 노드를 방문한 것으로 표시하고 출력
    visited[v] = true;
    std::cout << v << " ";

    // 현재 노드와 인접한 모든 노드를 재귀적으로 방문
    for (auto i = adjList[v].begin(); i != adjList[v].end(); ++i) {
        if (!visited[*i]) {
            DFSUtil(*i, visited);
        }
    }
}

// DFS 호출 함수 정의
void Graph::DFS(int v) {
    std::vector<bool> visited(vertices, false); // 모든 노드를 방문하지 않은 상태로 초기화

    // DFS 유틸리티 함수 호출
    DFSUtil(v, visited);
}

// 메인 함수
int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "정점 2에서 시작하는 깊이 우선 탐색: ";
    g.DFS(2);

    return 0;
}

설명

1. 그래프 클래스:
   • vertices: 그래프의 정점 수.
   • adjList: 각 정점의 인접 리스트를 저장하는 벡터.
2. addEdge 함수:
   • 정점 v에서 정점 w로의 간선을 그래프에 추가합니다.
3. DFSUtil 함수:
   • 현재 노드를 방문한 것으로 표시하고, 인접한 모든 노드를 재귀적으로 방문합니다.
4. DFS 함수:
   • 주어진 시작 정점에서 DFS를 수행합니다.
   • 방문 여부를 추적하기 위해 visited 벡터를 사용합니다.

DFS의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 탐색 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 24: 너비 우선 탐색 (BFS)"에 대해 학습하겠습니다.