/*
그래프를 인접 리스트 graph로 저장한다
graph[1] = [2, 3, 4]
graph[2] = [5]
graph[3] = [6, 7]
graph[4] = [8]
graph[6] = [9]
나머지 노드는 비어 있음

visited 배열을 만든다 (처음에는 모두 false)

dfs(현재노드) 함수를 만든다:

    현재노드를 방문 표시한다
    현재노드를 출력한다

    현재노드와 연결된 모든 이웃 노드를 순서대로 반복:
        next = 이웃 노드
        
        만약 next를 아직 방문하지 않았다면:
            dfs(next)   // 재귀 호출 (다시 깊이 들어가기)

main 함수에서:
    dfs(1)을 호출해서 탐색을 시작한다


#include <iostream>
#include <vector>
using namespace std;

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

void dfs(int node) {
    visited[node] = true;          // 방문 표시
    cout << node << " ";            // 출력

    // 연결된 노드 탐색
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (!visited[next]) {
            dfs(next);              // 재귀 호출
        }
    }
}

int main() {
    // 그래프 설정 
    graph[1] = {2, 3, 4};
    graph[2] = {5};
    graph[3] = {6, 7};
    graph[4] = {8};
    graph[5] = {};
    graph[6] = {9};
    graph[7] = {};
    graph[8] = {};
    graph[9] = {};

    dfs(1);   // 시작 노드 1

    return 0;
}

*/