본문 바로가기
C++ 알고리즘/6. 검색 알고리즘

깊이 우선 탐색 (DFS) // 스텍 사용

by Beijing_KingGod 2019. 9. 3.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
void dfs(int start,vector<vector <int>> temp) {
	vector <bool> check(temp.size(), false); // 방문한지 안한지
	stack<int> s;
	s.push(start);
	check[start] = true;
	cout << s.top() << endl;
	int index = start;
	int index2 = 0;
	while (!s.empty()) {	
		if (temp[index][index2] == 1&&check[index2]==false) {
			s.push(index2);
			check[index2] = true;
			cout << s.top() << endl;
			index = index2;
			index2 =0 ;
		}
		index2++;
		if (index2 == temp.size()) {
			index = s.top();
			s.pop();
			index2 = 0;
		}
	}

}
int main() {
	vector<vector<int>> temp = {
	{0,1,1,0,0,0,0},
	{1,0,1,1,1,0,0},
	{1,1,0,0,0,1,1},
	{0,1,0,0,1,0,0},
	{0,1,0,1,0,0,0},
	{0,0,1,0,0,0,1},
	{0,0,1,0,0,1,0}
	};
	for (int i = 0; i < temp.size(); i++) {
		for (int j = 0; j < temp[i].size(); j++) {
			cout << temp[i][j];
		}
		cout << endl;
	}
	dfs(0,temp);
	system("pause");
	return 0;
}
0110000
1011100
1100011
0100100
0101000
0010001
0010010
0
1
2
5
6
3
4​

출처:https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230945092&categoryNo=128&parentCategoryNo=0&viewDate=¤tPage=6&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=6

댓글