DFS(Depth First Search)

DFS(너비우선탐색) 알고리즘

BFS와 마찬가지로 맵 탐색을 하거나 최단거리를 찾을 때 사용된다.

DFS는 그래프나 트리에서 한 경로를 끝까지 따라간 뒤 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색하는 방식이다.

동작 원리

시작 노드에서 출발
아직 방문하지 않은 인접 노드를 하나 선택
그 노드를 이동하여 재귀적으로 같은 작업 수행
더 이상 방문할 곳이 없으면 이전 노드로 돌아옴(백트래킹)

구현 방법

DFS는 크게 두 가지 방식으로 구현할 수 있다.

1. 재귀 방식

C 언어의 함수를 재귀함수 형태로 구성하여 구현할 수 있다.

java

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs_recursive(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs_recursive(next);
        }
    }
}

int main() {
    int n = 5; // 노드 개수
    graph.assign(n + 1, {});
    visited.assign(n + 1, false);

    // 예시 간선 (양방향 그래프)
    graph[1] = {2, 3};
    graph[2] = {1, 4, 5};
    graph[3] = {1};
    graph[4] = {2};
    graph[5] = {2};

    dfs_recursive(1);
}

2. 스택

스택을 사용하여도 구현 가능하다.

java

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs_stack(int start) {
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int node = st.top();
        st.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";

            // 역순으로 넣어야 작은 번호 먼저 방문 가능
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (!visited[*it]) {
                    st.push(*it);
                }
            }
        }
    }
}

int main() {
    int n = 5; // 노드 개수
    graph.assign(n + 1, {});
    visited.assign(n + 1, false);

    // 예시 간선 (양방향 그래프)
    graph[1] = {2, 3};
    graph[2] = {1, 4, 5};
    graph[3] = {1};
    graph[4] = {2};
    graph[5] = {2};

    dfs_stack(1);
}

정리

vector<vector<int>> graph → 인접 리스트 저장
vector<bool> visited → 방문 여부 체크
재귀 방식은 코드가 간결하지만, 노드 개수가 많으면 스택 오버플로우의 위험이 있다.
스택 방식은 명시적으로 스택 사용 → 재귀 깊이 제한 문제가 없다.