반응형
풀이일시 : 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;
}
반응형
'알고리즘 문제풀이 > 기본문제풀이' 카테고리의 다른 글
[기본문제풀이] 분할정복 (0) | 2020.12.29 |
---|---|
[기본문제풀이] BFS 너비우선탐색 (0) | 2020.12.29 |
[기본문제풀이] greedy 알고리즘 (0) | 2020.12.29 |
[기본문제풀이] rabin karp 알고리즘 (0) | 2020.12.28 |
[기본문제풀이] KMP알고리즘 (0) | 2020.12.28 |
댓글