[이코테/DFS&BFS/C++] DFS & BFS 기초 설명 및 예제

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 

스택 자료구조 설명(선입후출)

스택 동작 예시

스택 구현 예제

stack<int> s; // 선언

s.push(x);

s.pop();

큐 자료구조(선입선출)

큐 구현 예제

queue<int> q; //큐 선언

q.push(x);

q.pop();

재귀함수 설명

재귀 함수의 종료 조건

DFS(Depth-First Search) 깊이 우선 탐색

- 그래프에서 깊은 부분을 우선적으로 탐색

- 스택 자료구조 혹은 재귀 함수 사용

#include <bits/stdc++.h>

using namespace std;

bool visited[9];
vector<int> graph[9];

void dfs(int x){
    visited[x] = true;
    cout << x << ' ';
    for(int i=0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visited[y]) dfs(y);
    }
}

int main(void) {
    /*그래프*/

    dfs(1);

    return 0;
}

BFS(Breadth-First Search) 너비 우선 탐색

- 그래프에서 가까운 노드부터 우선적으로 탐색

- 큐 자료구조 이용

#include <bits/stdc++.h>

using namespace std;

bool visited[9];
vector<int> graph[9];

void bfs(int start){
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout << x << ' ';
        for(int i=0; i<graph[x].size(); i++){
            int y = graph[x][i];
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    /*그래프*/

    bfs(1);

    return 0;
}