모든 경우의 수를 전부 탐색해야 하는 경우에 사용
DFS는 끝까지, BFS는 갈라진 모두 경우의 수를 탐색
DFS는 노드 끝까지 파고드는 것이므로 공간을 적게 쓰나, 최단 경로를 탐색하기 쉽지 않음
BFS는 최간 경로를 쉽게 찾을 수 있으나, 공간을 많이 쓰고 시간도 오래 걸릴 수 있다

DFS(Depth First Search)

• 방문하지 않은 원소를 계속해서 찾아감

1. 루트노드를 스택에 넣는다
2. 현재 스택의 노드를 빼서 visteid에 추가
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가
4. 반복
5. 스택이 비면 탐색을 종료

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        cur = stack.pop()
        visited.append(cur)
        for node in adjacent_graph[cur]:
            if node not in visited :
                stack.append(node)
    return visited


print(dfs_stack(graph, 1)) 

BFS(Breadth-first search)

• 너비 우선 탐색

1. 루트 노드를 큐에 넣는다
2. 현재 큐의 노드를 빼서 visited에 추가
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가
4. 2부터 반복
5. 큐가 비면 탐색을 종료

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    
    q = [start_node]
    visited =[]
    
    while q:
        cur = q.pop(0);
        visited.append(cur)
        for i in adj_graph[cur]:
            if i not in visited :
                q.append(i)
            
    return visited


print(bfs_queue(graph, 1))