스택 (stack) & 깊이 우선 탐색 (DFS)

- 스택 (stack)

https://www.youtube.com/watch?v=WB_BoAgWLNU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=14

 

https://blog.naver.com/ndb796/221230937978

13. 스택(Stack)

---

- 깊이 우선 탐색 (DFS)

https://www.youtube.com/watch?v=l0Rsu7dziws&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=17

 

https://blog.naver.com/ndb796/221230945092

16. 깊이 우선 탐색(DFS)

---

- 예제 코드

#include <iostream>
#include <vector>

using namespace std;

int number = 7;    // 그래프의 노드 수
int c[8];          // 방문 여부를 저장하는 배열
vector<int> a[8];  // 인접 리스트로 그래프를 표현하는 배열

void dfs(int x) {
    if (c[x]) return; // 노드를 이미 방문한 경우, 함수를 종료하고 돌아갑니다.
    c[x] = true; // 노드를 처음 방문한 경우, 방문 여부를 true로 표시합니다.
    cout << x << ' '; // 현재 노드를 출력합니다.

    for (int i = 0; i < a[x].size(); i++) {
        int y = a[x][i];
        dfs(y); // 현재 노드와 연결된 모든 인접 노드에 대해 재귀적으로 dfs 함수를 호출합니다.
    }
}

int main(void) {
    // 그래프의 간선을 설정합니다.

    // 1과 2를 연결합니다.
    a[1].push_back(2);
    a[2].push_back(1);

    // 1과 3를 연결합니다.
    a[1].push_back(3);
    a[3].push_back(1);

    // 2과 3를 연결합니다.
    a[2].push_back(3);
    a[3].push_back(2);

    // 2과 4를 연결합니다.
    a[2].push_back(4);
    a[4].push_back(2);

    // 2과 5를 연결합니다.
    a[2].push_back(5);
    a[5].push_back(2);

    // 3와 6를 연결합니다.
    a[3].push_back(6);
    a[6].push_back(3);

    // 3와 7을 연결합니다.
    a[3].push_back(7);
    a[7].push_back(3);

    // 4와 5를 연결합니다.
    a[4].push_back(5);
    a[5].push_back(4);

    // 6과 7을 연결합니다.
    a[6].push_back(7);
    a[7].push_back(6);

    // DFS를 수행합니다.
    dfs(1); // DFS를 시작 노드 1에서 시작합니다.

    return 0;
}