C++ DFS

---

<DFS>

-DFS는Depth First Search의 줄임말로 깊이 우선 탐색이라는 뜻이다.

-한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행한다

\

-재귀함수나 stack으로 구현할 수 있다.

---

 

<DFS과정>

1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다

 

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 하고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 

3. 2번의 과정을 수행할 수 없을 때까지 반복한다.

해가 없는 경로에 깊이 빠질 가능성이 있다.

---

<DFS장단점>

장점	목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점	해가 없는 경로에 깊이 빠질 가능성이 있다.

---

<DFS구현>

#include <iostream>
#include <vector>
#include <algorithm>

vector<int> graph[1001];
bool visitedDfs[1001];
void Dfs(int start)
{
    if (!visitedDfs[start])
    {
       cout << start << " ";
        visitedDfs[start] = true;
        for (int i = 0; i < graph[start].size(); i++)
        {
            Dfs(graph[start][i]);
        }
    }
}

---