DFS 기본 개념 및 구현 코드

Source: https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

DFS이다. 너비가 아니고 깊이를 우선으로 탐색하는 것을 의미한다. 위 사진의 동작을 보면 알 수 있음 

여기서 깊이라는 것은 시작 노드로부터 떨어진 거리라고 볼 수 있겠다. 

이를 좀 더 구체적으로 표현하면(컴퓨터의 사고방식으로 표현하면),

1. 어떤 탐색 시작 노드에서 시작하여, 간선으로 연결된 노드가 아직 방문되지 않은 노드라면

2. 무조건 그 간선을 먼저 따라가는 방식으로 구동되는 것이다.(이 때 재귀적인 방식이 이용된다.)

 

---

코드로 구현하면,(C++)아래와 같습니다

#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> adj; // Set Adjacency List
vector<bool> visited;

//dfs (node) 의 구현 parameter를 here이라는 탐색하고자 하는 노드를 받아서 탐색 시작함
void dfs(int here){
    visited[here] = true; // 탐색 시작 지점은 우선 visited로 마킹
    // 탐색 시작 노드로부터 인접 노드를 순회하면서 방문하지 않은 노드이면, 해당 노드로 이동하여 dfs 재귀 호출
    for(int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        if(!visited[there]){
            dfs(there);
        }
    }
}

// 위에서 정의 내린 dfs 함수를 이용하여 전체 노드들에 대해 탐색 수행
void dfsAll(){
    visited.resize(adj.size(),false);
    int count = 0;
    //모든 노드를 순서대로 순회하면서 방문하지 않은 노드를 기준으로 dfs 수행
    for(int i = 0; i < adj.size(); i++){
        if(!visited[i]){
        dfs(i);
        count++;
        }
    }
}