기록
[알고리즘] 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search) 본문
공부/Algorithm
[알고리즘] 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search)
aoieuo 2020. 7. 22. 15:121. DFS, Death-First Search (깊이 우선)
* 그래프 탐색의 경우 어떤 노드를 방문했었는지 반드시 검사해야한다 : 백트래킹
너비 우선 탐색과 마찬가지로 각 노드를 탐색할 때 사용된다. 너비 우선 탐색과 달리 스택을 사용한다. 사실 스택을 사용하지 않아도 구현이 가능 (재귀함수)
준비물: 스택, 그래프
-
스택의 최상단 노드를 확인한다.
-
최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다.
-
모든 인접노드에 방문한 후에는 스택의 최상단 노드를 뺀다.
위 세 과정을 반복하는 원리이다.
근데 대회에서는 빠르게 구현하고, 동작하게 하기 위해 재귀함수를 많이 쓴다. 아래 소스코드는 DFS를 재귀함수로 구현한 것이다.
#include <iostream>
#include <vector>
using namespace std;
int number = 7;
int c[7]; //방문 여부
vector<int> a[8];
void dfs(int x) {
if(c[x]) return; //이미 방문했을 경우
c[x] = true; //아닐 경우 방문 처리
cout << x << ' ';
for(int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
dfs(y); //y와 인접한 노드들을 방문! 재귀
}
}
2. BFS, Breath-First Search (폭 우선)
너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다.
준비물: 큐(Queue), 탐색할 그래프
-
큐에서 하나의 노드를 꺼낸다.
-
해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.
위 두 과정을 계속 반복한다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int number = 7;
int c[7];
vector<int> a[8];
void bfs(int start) {
queue<int> q;
q.push(start);
c[start] = true;
while(!q.empty()) {
int x = q.front();
q.pop();
printf("%d ", x);
for(int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if(!c[y]) {
q.push(y);
c[y] = true;
}
}
}
}
'공부 > Algorithm' 카테고리의 다른 글
BinaryTree (0) | 2020.09.30 |
---|---|
Searching (0) | 2020.09.30 |
[알고리즘] 동적 계획법 (Dynamic Programming) (0) | 2020.08.11 |
[알고리즘] 선택정렬, 버블정렬, 삽입정렬 - O(N^2) (0) | 2020.08.11 |
Greedy Algorithm (탐욕 알고리즘) (0) | 2020.07.05 |
Comments