DFS/BFS

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용합니다.

경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 됩니다.

 

DFS

깊이 우선 탐색입니다. 모든 경로를 탐색해야 할 경우에 적합하며 노드에서 다른 브랜치를 찾아보기 이전에 현재 브랜치를 모두 탐색한 후에 다음 브랜치를 탐색합니다.

스택 or 재귀를 통해서 구현할 수 있습니다. 하지만 재귀 또한 Stack Trace을 통해서 작동하는 것이기 때문에 본질은 같다고 할수있습니다.

 

시간 복잡도는 다음과 같습니다.
인접 행렬 : O(V^2)
인접 리스트 : O(V+E)

둘의 시간복잡도는 같으나 이 또한 구조체의 특징때문에 차이가 발생하는 것이지 동작 자체는 동일합니다. 

각 노드에 대해 탐색해야할 모든 브랜치를 탐색하게 되므로 인접행렬은 O(V^2)가 되는 것이고 인접리스트는 O(V+E)가 됩니다. 

 

아래의 코드는 인접행렬을 통해 구현하였습니다. 

const int ARRAY_SIZE = 100;
bool visited[ARRAY_SIZE];

void dfs(vector<vector<int>> &arr, int cur) {// 순회 노드를 출력합니다.
    cout<<cur<<" ";
    
    for (auto x: arr[cur]) {
        if(visited[x])continue;
        visited[cur] = true;
        dfs(arr,x);
    }
}

BFS

너비 우선 탐색입니다. 깊이 우선탐색과 다르게 현 노드에서 인접한 노드부터 탐색합니다. 

Queue을 통해 구현됩니다. 

 

시간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V+E)

너비 우선 탐색 역시 결국에는 해당 노드가 갖고있는 모든 edge에 대해 탐색을 해야 하므로 동일하게 시간복잡도를 가져가게 된다. 

따라서 대부분의 DFS로 풀수있는 문제는 BFS으로도 푸는것이 가능하다. 

 

const int ARRAY_SIZE = 100;
bool visited[ARRAY_SIZE];

void bfs(vector<vector<int>> &arr, int start) {// target을 찾는 DFS 함수
    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (auto x: arr[cur]) {
            if (visited[x])continue;
            visited[x] = true;
            q.push(x);
        }
        cout << cur << " ";
    }
}