[알고리즘] DFS 깊이 우선 탐색

DFS Depth-First Search 깊이 우선 탐색

출처: https://medium.com/@wendellrodrigues89/depth-first-search-traversal-trees-96169103d447

 

 

트리/그래프 구조에서 깊이를 우선하여 마지막 노드까지의 경로를 탐색하며 모든 노드를 탐색하는 알고리즘이다.

위 이미지와 같은 트리가 있을 때

- 루트 (9) 에서 시작

- 한쪽 브랜치를 최대한 깊이 탐색 (9-4-...)

- 마지막 자식 노드에 도달 (9-4-1)

- 부모 노드로 돌아옴 (9-4-...)

- 다른 쪽 브랜치를 최대한 깊이 탐색 (9-4-6)

 

이런 방식으로 모든 노드를 방문하는 것을 전위 순회 라고 부르기도 한다. pre-order traversal

 

위와 같이 같은 로직을 부분에 대해 순차적으로 진행하기에 재귀 또는 스택 형태로 구현할 수 있다.

단, 재귀 활용 시 깊이가 매우 깊은 경우 스택 오버플로우 위험이 있다.

또한 트리의 깊이를 모두 탐색하므로 빠른 알고리즘은 아니고, 모든 경우의 수를 탐색해야하는 경우에 사용할 수 있다.

 

인접 리스트 adjacency list

노드와 연결된 간선을 확인하기 위해 별도의 인접 리스트를 활용한다.

각 노드에 연결된 노드들을 2차원 벡터로 저장한다.

vector<vector<int>> adjList;

// u 와 v 버텍스 사이 간선 추가
void addEdge(int u, int v) {
	adjList[u].push_back(v);
    adjList[v].push_back(u); // 간선이 양방향인 경우
}

// v 가 u 의 인접 버텍스인지 확인 O(V) (u 에 인접한 버텍스 수)
bool isNeighbor(int u, int v) {
	for (int neighbor : adjList[u]) {
    	if (neighbor == v) return true;
    }
    return false;
}

 

그렇다면 앞서 말한 재귀 방식과 스택 방식으로 각각 어떻게 DFS 를 구현할지 코드를 살펴보자.

재귀

* 루트에서 모든 노드를 방문할 수 있다고 가정

* 노드는 한 번만 방문하며, 노드를 방문할 수 있는 또다른 경로가 있다고 해도 다시 방문하지 않음

--> 모든 경로를 확인하고 싶은 경우 백트래킹 활용

#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<bool> visited;
vector<int> currentPath; /* 모든 경로 체크하는 경우 */

void dfs_recursive(int u) {
    visited[u] = true;
   	
    /* PROCESS u HERE */
    
    for (int a : adj[u]) {
        if (!visited[a]) {
            dfs_recursive(a);
        }
    }
}

// n = number of vertices / e = number of edges
int dfs(int n, int e) {
    adj.resize(n);
    visited.resize(n, false);
    
    for (int i = 0; i < e; ++i) {
        int u, v;
        // HERE: GET U AND V VALUES FROM INPUT AND POPULATE THE ADJACENCY LIST
        adj[u].push_back(v);
        adj[v].push_back(u); // Only if the graph is undirected
    }
    
    int count = 0;
    dfs_recursive(0);
    return count;
}

 

스택 (iterative)

* 스택에 푸쉬할 때 반대 순서로 넣어 위 재귀와 순서를 동일하게 맞추었다.

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

vector<vector<int>> adj;
vector<bool> visited;

void dfs_iterative(int start) {
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int u = s.top();
        s.pop();

        if (visited[u]) continue;
        visited[u] = true;

        /* PROCESS u HERE */

        // Push neighbors onto the stack
        // (Optionally reverse adj[u] to match recursive DFS visiting order)
        for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
            if (!visited[*it]) {
                s.push(*it);
            }
        }
    }
}

// n = number of vertices / e = number of edges
int dfs(int n, int e) {
    adj.resize(n);
    visited.resize(n, false);
    
    for (int i = 0; i < e; ++i) {
        int u, v;
        // HERE: GET U AND V VALUES FROM INPUT AND POPULATE THE ADJACENCY LIST
        adj[u].push_back(v);
        adj[v].push_back(u); // Only if the graph is undirected
    }
    
    int count = 0;
    dfs_iterative(0);
    return count;
}

 

아래 문제는 DFS 를 활용할 수 있는 아주 간단한 예시이다.

프로그래머스

주목할 것은 합이 target이 되는 "모든 경우의 수"를 세어야 한다는 점이다. 이런 키워드를 볼 때 DFS 를 떠올리면 되겠다.

index + 1 을 하며 모든 요소에 대해 재귀 호출을 하고 있으며,

numbers 에 담긴 각 숫자에서 다음 숫자로 가는 연결이 sum+n 과 sum-n 이렇게 두 가지 있다고 보면 된다.

#include <vector>

using namespace std;

void dfs(const vector<int>& numbers, int index, int target, int sum, int& count) {
    if (index == numbers.size()) {
        if (sum == target)++count;
        return;
    }
    
    dfs(numbers, index + 1, target, sum + numbers[index], count);
    dfs(numbers, index + 1, target, sum - numbers[index], count);
}

int solution(vector<int> numbers, int target) {
    int count = 0;
    dfs(numbers, 0, target, 0, count);
    return count;
}