자료구조 알고리즘 DFS

DFS

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

 

 

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 = []

# 1. 시작 노드(루트 노드)인 1부터 탐색합니다.
# 2. 현재 방문한 노드를 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중에 방문하지 않은 노드에 방문합니다.
#
def dfs_recursion(adjacent_graph, cur_node, visited_array):

    visited_array.append(cur_node) # 1

    for adjacent_node in adjacent_graph[cur_node] : # 2 5 9
        if adjacent_node not in visited_array :
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)

    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

이렇게 작성하게 될경우 재귀함수 특성상 무한정 깊어지는 노드가 있는 경우 에러가 생길 수 있습니다!!

 

RecursionError !!

 

DFS를 스택으로 만들어보기

DFS 는 탐색하는 원소를 최대한 깊게 따라가야 합니다.

이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,

가장 마지막에 넣은 노드들만 꺼내서 탐색하면 됩니다.

가장 마지막에 넣은 노드들..? → 스택을 이용하면 DFS 를 재귀 없이 구현할 수 있습니다!

구현의 방법은 다음과 같습니다.

1. 루트 노드를 스택에 넣습니다.

2. 현재 스택의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.

4. 2부터 반복한다.

5. 스택이 비면 탐색을 종료한다.

그런데, 방문하지 않았다는 조건을 과연 어떻게 알 수 있을까요?

다 기록해놔야 알 수 있습니다.

이를 위해서 visited 라는 배열에 방문한 노드를 기록해두면 될 것 같습니다.

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 = [] # 방문한 걸 저장하기 위한 배열
stack = [1] # 시작 노드인 1을 넣어둔다.


1. 현재 스택에서 가장 마지막에 넣은 1을 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1]

2. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들인 [2, 5, 9]를 stack 에 추가합니다. 
# stack -> [2, 5, 9] visited -> [1]

3. 현재 스택에서 가장 마지막에 넣은 9을 빼서, visited 에 추가합니다. 
# stack -> [2, 5] visited -> [1, 9]

4. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들인 [10] 을 stack 에 추가합니다. 
# stack -> [2, 5, 10] visited -> [1, 9]

5. 현재 스택에서 가장 마지막에 넣은 10을 빼서, visited 에 추가합니다. 
# stack -> [2, 5] visited -> [1, 9, 10]

6. 인접한 노드들인 [9] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2, 5] visited -> [1, 9, 10]

7. 현재 스택에서 가장 마지막에 넣은 5를 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5]

8. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들인 [6, 8]를 stack 에 추가합니다. 
# stack -> [2, 6, 8] visited -> [1, 9, 10, 5]

9. 현재 스택에서 가장 마지막에 넣은 8를 을 빼서, visited 에 추가합니다. 
# stack -> [2, 6] visited -> [1, 9, 10, 5, 8]

10. 인접한 노드들인 [5] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2, 6] visited -> [1, 9, 10, 5, 8]

11. 현재 스택에서 가장 마지막에 넣은 6을 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6]

12. 인접한 노드들인 [5, 7] 에서 방문하지 않은 것들인 [7] 을 stack 에 추가합니다. 
# stack -> [2, 7] visited -> [1, 9, 10, 5, 8, 6]

13. 현재 스택에서 가장 마지막에 넣은 7를 을 빼서, visited 에 추가합니다. 
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6, 7]

14. 인접한 노드들인 [6] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.
# stack -> [2] visited -> [1, 9, 10, 5, 8, 6, 7]

15. 현재 스택에서 가장 마지막에 넣은 2를 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2]

16. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들인 [3] 을 stack 에 추가합니다. 
# stack -> [3] visited -> [1, 9, 10, 5, 8, 6, 7, 2]

17. 현재 스택에서 가장 마지막에 넣은 3을 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3]

18. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들인 [4] 를 stack 에 추가합니다. 
# stack -> [4] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

19. 현재 스택에서 가장 마지막에 넣은 4를 빼서, visited 에 추가합니다. 
# stack -> [] visited -> [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

20. 인접한 노드들인 [3] 에서 방문하지 않은 노드들이 없으니 추가하지 않습니다.

21. 현재 스택에서 꺼낼 것이 없습니다. DFS 가 끝났습니다.

 

# 1. 시작 노드를 스택에 넣습니다.
# 2. 현재 스택의 노드를 빼서 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가합니다.

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

    while stack : ## 스택이 비지 않을 때 까지 반복
        curr_node = stack.pop()
        visited.append(curr_node)
        for adjacent_node in adjacent_graph[curr_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)

    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!