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

깊이 우선 탐색 (Depth - First Search)

개념

DFS(깊이 우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

• 현재 정점에서 다음 분기로 넘어가기 전에 해당 분기를 완변하기 탐색
• 노드를 깊게 탐색

 

DFS 장점

1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간 수요 비교적 적음

2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음

3. 구현이 BFS보다 간단

 

 

DFS 단점

1. 단순 검색 속도는 BFS 보다 느림

2. 사전에 임의의 깊이를 지정 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로 탐색하도록 하는 것이 좋음

3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로 , 구한 해가 최단 경로가 된다는 보장이 없음.

   (목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)

 

 

방법

스택 또는 재귀함수로 구현

 

 

DFS 소스코드

재귀 방법

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10;

void DFS(int start, vector<int> graph[] , bool check[] ){
	check[start]=true;;
	cout<< start<<" "; //방문한 정점 출력 
	
	for(int i = 0 ; i< graph[start].size();i++){
		int next = v[start][i];
		
		if(!check[next]){//방문하지 않았다면 DFS 호출  
			DFS(next , graph, check);
		}
		
	}
	
}

int main(){
	int n,m,start; // 노드 개수 , 간선 개수 
	cin >> n >> m >> start;
	
	vector<int>graph[n+1];
	//visual studio 의 경우
	/* 변수 통해 배열 동적 생성 시 
		vector<int> * g = new vector<int>[n+1];
	*/ 
	bool check[n+1]={0,};
	
	for(int i = 0 ; i < m; i++){
		int u,v;
		cin >> u >> v;
		
		graph[u].push_back(v);
		graph[v].push_back(u);
		
	}
	
	//나중에 하나의 정점에서 다음 탐색 시 node 값 순차적으로
	//접근하고 싶으면 graph sort 하면 됨 
	
	DFS(start,graph,check);
	return 0;
}

 

stack 이용

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10;


//stack에 들어가면 방문한 것으로 판단
//해당 위치를 true로 해준다. 
void DFS(int start, vector<int> graph[] , int check[] ){
	
	stack<int> s;
	s.push(start);
	check[start]++;
	cout << start <<" ";
	
	while( !s.empty() ){
		int current = s.top();
		s.pop();
		
		for(int i = 0 ; i < graph[current].size() ; i++){
			
			int next = graph[current][i];
			
			if(!check[next]){
				cout<<next<<" ";
				check[next]++;
				
				s.push(current);//current로 다시 push 해야함. 
				s.push(next);
				break;//너비가 아니라 깊이 우선이라 
				
			}
			
		}
		 
	}
	 
	
}

int main(){
	int n,m,start; // 노드 개수 , 간선 개수 
	cin >> n >> m >> start;
	
	vector<int>graph[n+1];
	//visual studio 의 경우
	/* 변수 통해 배열 동적 생성 시 
		vector<int> * g = new vector<int>[n+1];
	*/ 
	int check[n+1]={0,};
	
	for(int i = 0 ; i < m; i++){
		int u,v;
		cin >> u >> v;
		
		graph[u].push_back(v);
		graph[v].push_back(u);
		
	}
	
	//나중에 하나의 정점에서 다음 탐색 시 node 값 순차적으로
	//접근하고 싶으면 graph sort 하면 됨 
	
	DFS(start,graph,check);
	return 0;
}

구현할 때 출력 어디서 해야하는지 생각하기

 

노드 개수가 많을 땐 visit bool로 하기!! 

 

 

참고

DFS

DFS BFS

백준 1260

DFS : 스택로 진행과정 설명