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

세상의 모든 알고리즘 - DFS

DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다. 이 알고리즘은 그래프의 모든 정점을 방문하는 방법 중 하나

DFS는 스택(Stack) 자료구조를 이용하여 구현 시작 정점을 스택에 넣고, 스택에서 정점을 꺼내어 방문하는 방식. 이때, 방문한 정점은 방문한 것으로 표시하고, 해당 정점과 인접한 정점들을 스택에 넣는다. 이후, 스택에서 다시 정점을 꺼내어 방문하고, 해당 정점과 인접한 정점들을 스택에 넣는 과정을 반복합니다. 이 과정에서 스택이 비어있게 되면 탐색을 종료함.

DFS는 그래프의 모든 정점을 방문하며, 이를 이용하여 그래프의 연결성을 파악하거나, 최단 경로를 찾는 등의 문제를 해결할 수 있습니다. 또한, DFS는 재귀적으로 구현할 수 있기 때문에 코드가 간단하며, 그래프의 깊이가 얕은 경우에는 BFS(Breadth-First Search)보다 빠른 속도를 보임. 하지만, 그래프의 깊이가 깊은 경우에는 스택이 많은 메모리를 차지하게 되어 성능이 저하될 수 있음

---

void dfs(int start, vector<int> graph[], bool check[]){

    check[start]= true;
    for(int i=0; i < graph[start].size(); i++){
        int next = graph[start][i];
        // 방문하지 않았다면
        if(check[next]==false){
            // 재귀함수를 호출한다.
            dfs(next, graph, check);
        }
    }

}

int main()
{
    int n,m,start;
    cin >> n >>m >> start;
    vector<int> graph[n+1];
    bool check[n+1];
    fill(check, check+n+1,false);
    for(int i=0; i<m; i++)
    {
        int u,v;
        cin >> u >>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(int i=0; i<=n; i++)
    {
        sort(graph[i].begin(), graph[i].end());
    }
    dfs(start,graph,check);
    return 0;

}