DFS

DFS(깊이 우선 탐색)

 

: stack, 재귀함수, check 사용

: 멀리 있는 노드를 우선으로 탐색하는 알고리즘

=> 최단거리 + 가중치(이동과정 제약) 경우 사용 

 

def dfs(graph,start_node):
    visited = list() #queue
    stack = list() #stack 

    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node])
    
    return visited

 

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89