DFS 깊이 우선 탐색

DFS : Depth Frist Search : 깊이 우선 탐색

출처 : 나무위키

트리나 그래프에서 특정 노드를 시작으로 다음 노드를 탐색하며 갈림길을 만나면 저장해놨다가 진행하는 루트의 끝에 도달했을 때 갈림길로 돌아가 다른 다음 노드를 탐색한다

이러한 방법으로 모든 노드를 탐색하는 것을 DFS라고 한다

 

대표적인 예로 백트래킹이 있다

백트래킹은 DFS와 동일하지만, 조건을 만족 시킬 경우에만 다음 노드로 넘어간다는 점에서 루트의 끝에 도달하는 DFS와 차이가 있다

 

재귀와 스택으로 구현 가능하며,

재귀 형태일 때는 순환 그래프면 안된다는 제한 사항과 스택 형태일 때는 스택 오버플로우에 유의해야한다는 특징이 존재한다

 

경로 탐색, 그룹 찾기, 사이클 검출 등에서 활용 가능하다

 

재귀

// 재귀 DFS
void dfs(int node, vector<int> graph[], bool visited[])
{
	visited[node] = true;
    
    std::cout << node << ' ';
    
    for (int i = 0; i < graph[node].size(); i++)
    {
    	int next = graph[node][i];
        
        if (!visited[next])
        {
        	dfs(next, graph, visited);
        }
    }
}

// 방문 체크용 배열 생성
bool visited[노드 개수 + 1] = {false};

// 그래프 생성
vector<int> graph[노드 개수 + 1];

for (int i = 0; i < 간선 개수; i++)
{
	int x, y;
    
    std::cin >> x >> y;
    
    graph[x].push_back(y);
    graph[y].push_back(x);
}

for (int i = 1; i <= 노드 개수; i++)
{
	std::sort(graph[i].begin(), graph[i].end());	// #include <algorithm>
}

// DFS 사용
dfs(시작할 노드 번호, graph, visited);

 

스택

// 스택 DFS
void dfs(int node, vector<int> graph[], bool visited[])
{
	std::stack<int> s;
    
    s.push(node);
    vistied[node] = true;
    
    std::cout << node << ' ';
    
    while (!s.empty())
    {
    	int current = s.top();
        s.pop();
        
        for (int i = 0; i < graph[current].size(); i++)
        {
        	int next = graph[current][i];
            
            if (!visited[next])
            {
            	visited[next] = true;
                
                std::cout << next << ' ';
                
                s.push(current);
                s.push(next);
                
                break;
            }
        }
    }
}

// 방문 체크용 배열 생성
bool visited[노드 개수 + 1] = {false};

// 그래프 생성
vector<int> graph[노드 개수 + 1];

for (int i = 0; i < 간선 개수; i++)
{
	int x, y;
    
    std::cin >> x >> y;
    
    graph[x].push_back(y);
    graph[y].push_back(x);
}

for (int i = 1; i <= 노드 개수; i++)
{
	std::sort(graph[i].begin(), graph[i].end());	// #include <algorithm>
}

// DFS 사용
dfs(시작할 노드 번호, graph, visited);

 

 

기본적인 구현은 이렇게 하고, 활용은 알아서,,