[Algorithm][Template] DFS와 BFS

	DFS	BFS
동작원리	스택	큐
구현방법	*재귀함수 이용	큐 자료구조 이용
시간복잡도	O(N)	O(N)

*재귀함수 : 자기 자신을 다시 호출하는 함수, 종료조건을 반드시 명시해야 한다.

 

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (방문처리 순서가 중요하다. 스택에 삽입되면서 준비상태가 되면 방문처리가 되어야 한다.)
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

    - 재귀함수 자체가 스택형식으로 작동한다. (함수호출 - 스택에 삽입, 함수 종료 - 스택에서 제거)

    - 즉, DFS는 재귀함수를 이용하면 스택을 따로 선언하여 사용할 필요가 없다. 따라서 BFS보다 구현이 간편하다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > graph = {
    vector<int> {},
    vector<int> {2, 3, 8},
    vector<int> {1, 7},
    vector<int> {1, 4, 5},
    vector<int> {3, 5},
    vector<int> {3, 4},
    vector<int> {7},
    vector<int> {2, 6, 8},
    vector<int> {1, 7}
};
bool visited[101];

// DFS 함수 정의
// 탐색 시작 노드 스택 삽입
void dfs(int now) {
    // 현재 노드를 방문 처리
    visited[now] = true;
    cout << now << " ";
    // 현재 노드의 인접 노드 중 방문하지 않은 노드 재귀적으로 방문
    for (int next : graph[now]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
// 현재(최상단) 노드 스택에서 꺼내기
}
int main(void) {

    dfs(1);
    cout << "\n";

    return 0 ;
}

 

BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 전부 큐에 삽입하고 방문처리를 한다. (방문처리 순서가 중요하다. 큐에 삽입되면서 준비상태가 되면 방문처리가 되어야 한다.)
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

    - 일반적인 경우 BFS가 DFS보다 성능이 좋다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int> > graph = {
    vector<int> {},
    vector<int> {2, 3, 8},
    vector<int> {1, 7},
    vector<int> {1, 4, 5},
    vector<int> {3, 5},
    vector<int> {3, 4},
    vector<int> {7},
    vector<int> {2, 6, 8},
    vector<int> {1, 7}
};
bool visited[101];

// BFS 함수 정
void bfs(int start) {
    queue<int> q;

    // 탐색 시작 노드 큐에 삽입
    q.push(start);
    // 현재 노드를 방문 처리
    visited[start] = true;
    
    // 큐가 빌때까지 반복
    while(!q.empty()) {
        // 큐에서 원소 하나 뽑기
        int now = q.front();
        cout << now << " ";
        q.pop();

        // 해당 원소와 연결된, 아직 방문하지 않은 노 큐에 삽입 후 방문처리
        for (int next : graph[now]){
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}
int main(void) {

    bfs(1);
    cout << "\n";

    return 0 ;
}

 

결론

      트리의 깊이를 묻는 문제는 BFS를 사용하자. 둘 다 사용할 수 있어도 BFS를 쓰자.