DFS (깊이 우선 탐색)

💡 DFS란?

DFS (Depth First Search) 는 그래프의 한 정점에서 시작하여 더 이상 갈 수 없을 때까지 계속 깊이 들어가며 탐색하는 알고리즘입니다.

✅ 특징

• 스택(Stack) 혹은 재귀 함수로 구현 가능
• 한 방향으로 계속 들어가다가, 막히면 이전으로 돌아옴 (Backtracking)
• 그래프의 모든 정점을 탐색하거나 연결된 컴포넌트만 순회할 때 유용

---

📌 탐색 방식 비교

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
방식	최대한 깊이 먼저 탐색	가까운 노드부터 탐색
자료구조	스택(재귀 포함)	큐
활용	경로 탐색, 사이클 검사	최단 거리 탐색

---

🧠 DFS 작동 순서 (예제 그래프 기반)

그래프 설명

• 정점: 0 ~ 5
• 방향 그래프 (Directed Graph)
• 가중치 존재 (하지만 DFS에서는 가중치 사용 X)

DFS 순서 예시 (0번에서 시작)

0 → 1 → 2 → 3 → 4
(5번은 연결되어 있지 않으면 탐색 안 됨)

---

🛠 DFS 코드 (인접 리스트 버전)

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

struct Vertex {};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;

void CreateGraph()
{
    vertices.resize(6);
    adjacent = vector<vector<int>>(6);

    // 인접 리스트 초기화
    adjacent[0] = { 1, 3 };
    adjacent[1] = { 0, 2, 3 };
    adjacent[3] = { 4 };
    adjacent[5] = { 4 };
}

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

    for (int there : adjacent[here])
    {
        if (!visited[there])
            Dfs(there);
    }
}

void DfsAll()
{
    visited = vector<bool>(6, false);
    for (int i = 0; i < 6; i++)
        if (!visited[i])
            Dfs(i);
}

int main()
{
    CreateGraph();
    DfsAll();
}

---

🛠 DFS 코드 (인접 행렬 버전)

void CreateGraph()
{
    vertices.resize(6);
    adjacent = vector<vector<int>>
    {
        { 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 1, 0 },
        { 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 1, 0 },
    };
}

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

    for (int there = 0; there < 6; ++there)
    {
        if (adjacent[here][there] == 0)
            continue;

        if (!visited[there])
            Dfs(there);
    }
}

---

⚠️ 주의사항

1. 무한 루프 방지
   → 방문한 정점을 visited 배열로 체크!

2. 끊긴 노드 처리
   → Dfs(0) 만 호출하면 0번과 연결된 노드만 탐색됨
   → DfsAll() 함수로 모든 정점에서 시작 시도 필요

---

📚 DFS 호출 흐름

Dfs(0)
// → Dfs(1)
//   → Dfs(2)
//   → Dfs(3)
//     → Dfs(4)
// 5번은 연결 안 돼 있어서 탐색 안 됨

---

🔎 DFS vs BFS 활용 예시

상황	사용 알고리즘
미로 탈출	BFS (최단 경로 탐색)
사이클 검사	DFS
경로 존재 여부	DFS
트리 순회	DFS