[개념] DFS/BFS

스택

• 박스 쌓기에 비유
• 선입후출 구조 혹은 후입 선출 구조

큐

• 놀이공원 줄서기 비유
• 선입선출 구조

queue 보다는 deque 구조 사용
스택과 큐의 장점을 택한것이고 데이터를 넣고 뺴는 속도가 리스트 자료형에 디배 효율적이며 queue라이브러리를 사용하는 것 보다 간단하다

재귀함수

• 자기자신을 호출하는 함수
• 재귀함수 사용시 스택 자료 구조 이용
• 함수를 계속 호출했을 때 가장 마지막에 호출함 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨

재귀 함수 사용시 재귀함수가 언제 끝나고, 종료할지 꼭 명시

 

---

팩토리얼 예제

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
int answer = 0;
int factorial(int n) {
    // n = 1 인경우 재귀함수 멈춤
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int num;
    cin >> num;

    cout<<factorial(num);

}

---

DFS 스택 자료구조

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드를 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리,
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

cf ) 방문 처리 - 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것

BFS

• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 선입선출 방식인 큐 자료구조 사용
• 인접한 노드를 반복적으로 큐에 놓도록 알고리즘 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게됨

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함
2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

너비 우선 탐색은 DFS보다 수행시간이 좋음

 

dfs / bfs 비교