[알고리즘] 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search)

1. DFS, Death-First Search (깊이 우선)

* 그래프 탐색의 경우 어떤 노드를 방문했었는지 반드시 검사해야한다 : 백트래킹

 

Depth <-> Breadth

너비 우선 탐색과 마찬가지로 각 노드를 탐색할 때 사용된다. 너비 우선 탐색과 달리 스택을 사용한다. 사실 스택을 사용하지 않아도 구현이 가능 (재귀함수)

 

준비물: 스택, 그래프

1. 스택의 최상단 노드를 확인한다.

2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다.

3. 모든 인접노드에 방문한 후에는 스택의 최상단 노드를 뺀다.

위 세 과정을 반복하는 원리이다.

근데 대회에서는 빠르게 구현하고, 동작하게 하기 위해 재귀함수를 많이 쓴다. 아래 소스코드는 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), 탐색할 그래프

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

위 두 과정을 계속 반복한다.

#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;
            }
        }
    }
}