알고리즘 :: DFS 깊이 우선 탐색 (C/C++ 구현), 탐색 알고리즘

DFS 깊이 우선 탐색

DFS도 BFS처럼 탐색 알고리즘 중 하나다.

 

BFS는 큐(Queue)를 이용했다면,

DFS는 스택(Stack)이나 재귀함수를 이용해서 구현한다.

 

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 탐색을 할때 사용한다.

응용하여 미로찾기와 같은 게임을 만들 수 있다. 

1을 방문

1과 인접한 2를 방문

2와 인접한 3을 방문

댓글을 하나 달아주셔서 추가 설명드리자면..

2번 노드와 3번 노드가 연결되어 있는 상태입니다. 그렇기 때문에 3번을 먼저 방문하는것이 맞습니다. (2020.02.13 업데이트)

 

3과 인접한 6을 방문

6과 인접한 노드가 없으므로, 6을 스택에서 뺀다.

3과 인접한 노드 중에서 방문하지 않은 7을 방문

7과 인접한 노드가 없으므로, 인접한 노드가 생길때까지 스택에서 값을 뺀다. 7을 빼고 3을 뺀다.

 

2와 인접한 4를 방문한다.

4와 인접한 8을 방문한다.

 

8과 인접한 노드가 없으므로, 스택에서 뺀다. 4도 뺀다.

2와 인접한 5를 방문한다.

 

5와 인접한 9를 방문 한다.

 

결국, 방문 순서는

1 2 3 6 7 4 8 5 9 가 된다.

 

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int number = 9;
int visit[9];
vector<int> a[10];

void dfs(int start){
    if(visit[start]){
        // 방문한경우 바로 빠져나옴 
        return;
    }
    
    visit[start] = true; // 방문
    printf("%d ", start);
    
    for(int i=0; i< a[start].size(); i++){
        // 인접한 노드를 방문 
        int x = a[start][i];
        dfs(x);
    }
}

int main(void){
    // 1과 2를 연결 
    a[1].push_back(2);
    a[2].push_back(1);
    
    // 1과 3을 연결 
    a[1].push_back(3);
    a[3].push_back(1);
    
    // 2과 3을 연결 
    a[2].push_back(3);
    a[3].push_back(2);
    
    // 2와 4를 연결 
    a[2].push_back(4);
    a[4].push_back(2);

    // 2와 5를 연결 
    a[2].push_back(5);
    a[5].push_back(2);
    
    // 4와 8을 연결 
    a[4].push_back(8);
    a[8].push_back(4);
    
    // 5와 9를 연결 
    a[5].push_back(9);
    a[9].push_back(5);
    
    // 3과 6을 연결 
    a[3].push_back(6);
    a[6].push_back(3);
    
    // 3과 7을 연결 
    a[3].push_back(7);
    a[7].push_back(3);
    
    // 1번 노드부터 bfs 탐색 실행 
    dfs(1);
    
    return 0;
} 
​

 

 

관련 글

2018/04/30 - [Algorithm] - 알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색 알고리즘

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘