알고리즘 공부[2] DFS(깊이 우선 탐색) (C++)

안녕하세요. 오늘은 그래프에 대해서 가장 많이 등장하는 DFS에 관하여 알아보겠습니다.

DFS는 매년 여러 곳의 입사시험 및 프로그래밍 대회에서 등장합니다.

Contents

DFS(Depth-First search)

DFS구현(1) Recursive

DFS구현(2) Stack

DFS의 time complexity

DFS(Depth-First Search)

---

DFS란 무엇일까요? 한국말로 해석해보면 깊이 우선 탐색이라는 말이 됩니다. 

그래프에서 특정 정점을 찾을 때 그래프의 깊이를 우선적으로 탐색한다는 말이죠. 이렇게 말하면 솔직히 감이 잘 안옵니다.

예를 봅시다!

https://steemitimages.com/0x0/https://janav.files.wordpress.com/2014/01/dfs-bfs-difference.jpeg

위의 그림은 DFS와 BFS의 작동 순서를 점선화살표로 나타내줍니다.

오른쪽과 왼쪽의 차이가 느껴지시나요? 아마 그림을 보고나면 살짝 직관적인 감을 잡으셨을 것입니다.

DFS는 한 정점 기준으로 해당 정점과 연결되어 있는 정점으로 계속적으로 방문하게 됩니다.

(a->b->d->h->e->i->j->c->f->k->g)

좀더 정확한 이해를 위해 슈도코드를 살펴봅시다. 아래는 재귀적으로 정의한 알고리즘의 슈도코드입니다.

DFS 알고리즘은 한 정점과 인접해 있는 정점 중 아직 방문하지 않은 정점을 보게됩니다.

  그렇다면 DFS 알고리즘을 구현함에 있어서 몇가지 중요한 정보들은 무엇이 있을까요?  

1) 방문한 정점을 알아야 합니다. 따라서 각 정점의 방문 여부를 저장하는 자료구조가 필요합니다.

방문한 정점이라면 들릴 필요가 없기 때문이죠! (방문한 정점이라면 그 정점 기준으로 모든 depth를 이미 봤기 때문입니다.)

2) 더이상 방문 할 정점이 없으면 이전의 정점으로 돌아가야 합니다. 

위에 제시한 그림에서 보면 h를 방문하고 다시 b로 돌아가 e로 나아가는 방식처럼 말이죠.

그렇기 때문에 이를 구현하는 방법이 필요합니다. 이는 재귀적으로 호출하거나, stack을 이용하면 구현이 가능합니다.

3) 마지막으로 고려할 중요한 한가지가 있습니다. 

보통 그래프가 주어질 때 사람들은 주어진 그래프가 딱 하나로 이루어 진 것으로 생각합니다.

알고리즘 문제를 푸는데에 있어서 그래프가 분리되어 있을 수도 있다는 사실을 고려하지 않습니다. 

바로 이러한 함정에 유의해야 합니다.

그래프가 입력 sequence로 주어지면 해당 그래프가 1개인지 2개인지는 모릅니다. (물론 문제마다 다릅니다만) 

따라서 주어진 그래프의 모든 정점을 담고 있는 자료구조를 만들어서, 모든 정점에 대해 dfs가 이루어 졌는지(모든 정점이 방문되어있는 상태인지) 살펴보아야 합니다.

DFS구현(1)-Recursive

---

이제 DFS를 어떻게 구현하는가를 코드로 알아보겠습니다. 아래 코드는 DFS를 재귀적으로 호출하는 방식으로 만든 코드입니다.

#include<iostream>
#include<vector>
using namespace std;
 
int V_size;                     //주어진 그래프의 Vertex개수(|V|)
vector< vector<int> > adjacent; //인접 행렬의 표현(|V|x|V|)
vector<bool> visited(V_size, false);
 
void dfs(int here) {
    cout << "VISIT : " << here << '\n';
    visited[here] = true;         //방문 표시
    for (int i = 0; i < V_size; i++) {
        if (adjacent[here][i] != 0 && !visited[i])
            dfs(i);
    }
}
 
void dfsAll(){ //모든 정점에 대해서 dfs수행을 합니다.
/*
그래프가 여러개 일 수 있으므로 모든 정점에 대해 수행하여야 합니다.
*/
    visited = vector<bool>(V_size,false);
    for(int i = 0; i < V_size; i++){
        if(!visited[i])
            dfs(i);
    }
}

여기서 주의깊게 보아야 할 것은 dfsAll()입니다.

다시 한번 말씀드리지만 한 정점에 대해서만 그래프를 보게 되면 주어진 정점과 분리되어 있는 그래프를 보지 못합니다.

만약 인접리스트 표현방식을 쓴다면 아래와 같습니다.

#include<iostream>
#include<vector>
using namespace std;
 
vector< vector<int> > adjacent; //인접 리스트의 표현
vector<bool> visited(adjacent.size(), false);
 
void dfs(int here) {
    cout << "VISIT : " << here << '\n';
    visited[here] = true;
    for (int i = 0; i < adjacent[here].size(); i++) {
        if (!visited[i])
            dfs(i);
    }
}
 
void dfsAll(){
    visited = vector<bool>(adjacent.size(),false);
    for(int i = 0; i < adjacent.size(); i++){
        if(!visited[i])
            dfs(i);
    }
}
 

DFS구현(2)-Stack

---

앞서 말씀드렸듯이 방문을 재귀적으로 하지않고, stack을 이용하여 구현 할 수도 있습니다.

stack으로 구현할 경우 재귀적으로 방문 하는것 보다는 함수 호출에 대한 overhead가 줄어들어 속도가 조금 향상됩니다.

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int V_size;
vector< vector<int> > adjacent; //인접 행렬의 표현
vector<bool> visited(V_size, false);
stack<int> mem;
 
void dfs(int start) {
    int current = start;
    mem.push(current); 
    visited[current]=true;
    cout << "VISIT : " << start << '\n';
    while(mem.size()){
        current = mem.top();
        for(int i = 0; i < V_size; i++){
            if(adajacent[current][i]!=0 && !visited[i]){
                current = i;
                mem.push(current);
                visited[current]=true;
                cout << "VISIT : " << current << '\n';
                break;
            }else if(i == V_size-1){
                //연결된 정점이 없거나 정점 중 방문할 정점이 없는 경우
                mem.pop();
            }
        }
    }
}
 
void dfsAll(){
    visited = vector<bool>(adjacent.size(),false);
    for(int i = 0; i < adjacent.size(); i++){
        if(!visited[i])
            dfs(i);
    }
}
 

DFS의 time complexity

---

이제 알고리즘을 어느정도 공부 했으니, DFS의 성능을 살펴 봅시다.

DFS의 time complexity는 구현 방식에 따라 차이가 있습니다.

그래프의 표현을 인접리스트로 하느냐, 인접행렬로 하느냐에 따라 다릅니다.

1) 인접리스트 방식의 time complexity

인접 리스트 방식을 사용하면 DFS는 각 정점마다, 간선마다 호출이 됩니다. 즉,

이 됩니다.

2) 인접행렬 방식의 time complexity

인접 행렬 방식을 사용하면 DFS가 |V|만큼 호출이 되고 각 정점마다 연결된 정점을 찾는데 무조건 |V|만큼의 시간이 듭니다. 따라서

이 됩니다.

---

이번 글에서는 DFS에 대해 살펴 보았습니다.

질문이 있으시거나, 잘못된 부분을 발견하셨다면 언제든지 댓글 남겨주시면 응답하겠습니다.

다음 글에서는 DFS와 함께 공부하면 좋은 위상정렬에 대하여 다루어 보겠습니다.

감사합니다.