DFS

DFS 개념

한 줄 정의

• DFS(Depth-First Search)는 한 정점에서 시작해 한 경로를 끝까지 내려간 뒤,
  막히면 되돌아와 다른 경로를 탐색하는 방식입니다.

동작 원리 (핵심)

1. 현재 정점을 방문 처리한다.
2. 인접 정점 중 미방문 정점으로 이동한다.
3. 더 갈 곳이 없으면 직전 정점으로 되돌아간다(백트래킹).
4. 시작점에서 도달 가능한 모든 정점을 방문할 때까지 반복한다.

DFS vs BFS (절대 헷갈리면 안 되는 것)

항목	DFS	BFS
탐색 성향	깊이 우선	너비 우선
핵심 자료구조	스택(재귀 호출 스택 포함)	큐
비가중치 최단거리	보장 안 함	보장

DFS가 자주 쓰이는 문제

• 연결 요소(컴포넌트) 개수 세기
• 사이클 존재 여부 검사
• 위상 정렬(방향 비순환 그래프)
• 백트래킹 기반 탐색(조합/경로 생성 등)

---

DFS 구현 패턴

인접 리스트 + 재귀 (가장 기본)

int V = 6;
vector<vector<int>> adj(V);
vector<bool> visited(V, false);

void Dfs(int here) {
    visited[here] = true;
    cout << "Visited: " << here << '\n';

    for (int there : adj[here]) {
        if (visited[there]) continue;
        Dfs(there);
    }
}

핵심 포인트:

• visited[here] = true는 재귀 호출 전에 해야 중복 방문을 막을 수 있습니다.
• 인접 리스트는 이웃 순회가 deg(here)만큼만 돌아 효율적입니다.

인접 행렬 + 재귀

int V = 6;
vector<vector<int>> matrix(V, vector<int>(V, 0)); // 0: 미연결, 1: 연결
vector<bool> visited(V, false);

void DfsMatrix(int here) {
    visited[here] = true;
    cout << "Visited: " << here << '\n';

    for (int there = 0; there < V; there++) {
        if (matrix[here][there] == 0) continue;
        if (visited[there]) continue;
        DfsMatrix(there);
    }
}

스택으로 구현한 반복형 DFS

void DfsIterative(int start) {
    vector<bool> visited(V, false);
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int here = st.top();
        st.pop();
        if (visited[here]) continue;

        visited[here] = true;
        cout << "Visited: " << here << '\n';

        // 방문 순서를 재귀와 유사하게 맞추려면 역순 push를 고려
        for (int i = static_cast<int>(adj[here].size()) - 1; i >= 0; i--) {
            int there = adj[here][i];
            if (!visited[there]) st.push(there);
        }
    }
}

• 재귀 깊이가 깊어질 수 있는 대형 입력에서는 반복형 DFS가 안정적일 수 있습니다.

---

끊긴 그래프 전체 탐색 (중요)

왜 필요한가?

• 시작점을 하나만 잡으면, 해당 컴포넌트만 방문합니다.
• 전체 그래프를 보려면 모든 정점을 순회하면서 미방문 정점에서 DFS를 새로 시작해야 합니다.

전체 DFS + 컴포넌트 개수

int DfsAll() {
    fill(visited.begin(), visited.end(), false);
    int componentCount = 0;

    for (int v = 0; v < V; v++) {
        if (visited[v]) continue;
        Dfs(v);
        componentCount++;
    }

    return componentCount;
}

• componentCount는 연결 요소 수를 의미합니다.

---

시간/공간 복잡도

표현 방식	시간 복잡도	이유
인접 리스트	O(V + E)	각 정점/간선을 최대 한 번씩 처리
인접 행렬	O(V^2)	각 정점마다 전체 정점 V를 스캔

공간 복잡도:

• visited: O(V)
• 재귀 DFS: 호출 스택 최대 O(V) (편향 그래프 최악)
• 반복 DFS: 명시적 스택 최대 O(V)

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
visited 체크 전에 재귀 호출	무한 재귀/중복 방문
Dfs(start)만 호출하고 끝냄	끊긴 컴포넌트 누락
DFS/BFS 자료구조 혼동	구현·설명 오류
재귀 깊이 한계 무시	대형 입력에서 스택 오버플로우 가능

체크 질문 (스스로 답해보기)

• DFS에서 visited를 “호출 전에” 찍어야 하는 이유는?
• 인접 리스트 DFS가 O(V + E)가 되는 직관은?
• 왜 DfsAll()이 없으면 전체 그래프를 못 볼 수 있을까?
• 재귀 DFS 대신 반복 DFS를 택해야 하는 상황은?

---