[기본문제풀이] DFS 깊이우선탐색

 

풀이일시 : 2020-08-30

​

 

DFS :

깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다.

아래그림이 dfs를 한눈에 보여준다고 생각한다

출처 : http://www.aistudy.com/heuristic/depth-first_search.htm

​

 

문제 :

DFS를 구현하라

​

 

풀이 :

recursive하게 구현한다.

 

#include <iostream>
#include <vector>
#define MAX 9

using namespace std;
int d[MAX] = { 0, }; //방문체크하는배열
vector<int> a[MAX];

void dfs(int x) {
	if (d[x] == 1)
		return;
	d[x] = true;//방문체크하기
	cout << x << ' ';
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		dfs(y); // 재귀의 방법으로 dfs 실행
	}
}

int main() {
	a[1].push_back(2);
	a[2].push_back(1);

	a[1].push_back(3);
	a[3].push_back(1);

	a[1].push_back(8);
	a[8].push_back(1);

	a[2].push_back(7);
	a[7].push_back(2);

	a[7].push_back(6);
	a[6].push_back(7);

	a[7].push_back(8);
	a[8].push_back(7);

	a[3].push_back(4);
	a[4].push_back(3);

	a[3].push_back(5);
	a[5].push_back(3);

	a[4].push_back(5);
	a[5].push_back(4);

	dfs(1);
	return 0;
}