깊이 우선 탐색. Depth First Search(DFS)

깊이 우선 탐색. Depth First Search(DFS)

 

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

다음과 같은 간단한 알고리즘에 따라 작동
1. 스택의 최상단 노드 확인.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리.
    방문하지 않은 인접노드가 없으면 스택에서 최상단 노드 빼기.

backtracking

#include <iostream>
#include <vector>

using namespace std;

// 총 7개의 노드가 인접한 노드를 가질 수 있도록.
int number = 7;
int arr[8];
vector<int> v[8];

int y;

void dfs(int n){

    if(arr[n]) return; // 현재 노드를 방문했다면 함수 끝내기
    
    arr[n] = true; // 방문처리
    
    cout << n << ' '; // 출력
    
    // 재귀
    // 방문이 가능한 인접 노드들이 여러 개 있는 경우에 작은 수 먼저 탐색
    for(int i = 0; i < v[n].size(); i++){
    	y = v[n][i];
        dfs(y);
    }
}

int main() {
	// 1과 2을 연결
	v[1].push_back(2);
	v[2].push_back(1);
	// 1과 3을 연결
	v[1].push_back(3);
	v[3].push_back(1);
	// 2와 3을 연결
	v[2].push_back(3);
	v[3].push_back(2);
	// 2와 4을 연결
	v[2].push_back(4);
	v[4].push_back(2);
	// 2와 5를 연결
	v[2].push_back(5);
	v[5].push_back(2);
	// 3과 6을 연결
	v[3].push_back(6);
	v[6].push_back(3);
	// 3과 7을 연결
	v[3].push_back(7);
	v[7].push_back(3);
	// 4과 5을 연결
	v[4].push_back(5);
	v[5].push_back(4);
	// 6과 7을 연결
	v[6].push_back(7);
	v[7].push_back(6);
	
	dfs(1);
	
	return 0;
}

16. 깊이 우선 탐색(DFS)

[Algorithm] C++에서 그래프 탐색(DFS와 BFS) 구현하기

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전