DFS(Depth First Search) - 깊이 우선 탐색

DFS란?

자료의 검색, 트리나 그래프를 탐색하는 방법으로 사용되며 

한 노드를 시작으로 인접한 다른 노드를 통해 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 

DFS의 특징

DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 

따라서 공간을 적게쓰지만 최단 경로를 탐색하기가 쉽지 않다.

 

DFS 구현 방법

1. 재귀함수

DFS는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다.

1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문
2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드 방문
3. 만약 끝에 도달했다면 리턴

-> 반복.. 반복하다가 갈 수 없게 되면 탈출 -> 재귀 함수를 쓰면 되겠구나

 

코드로 직접 살펴보자

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_recursion(adjacent_graph, curr_node, visited_arr):
    # 1. 시작 노드(루트 노드)인 1부터 탐색
    # 2. 현재 방문한 노드를 visited_arr에 추가
    # 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문

    visited_arr.append(curr_node)
    for adjacent_node in adjacent_graph[curr_node]:
        # print(adjacent_node, visited_arr) # 이 부분을 출력해서 과정을 보면 이해하기 쉽다
        if adjacent_node not in visited_arr:  # 이 부분이 탈출 조건
            dfs_recursion(adjacent_graph, adjacent_node, visited_arr)


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

이렇게 재귀함수를 통해 DFS를 구현할 수 있다.

하지만 재귀함수를 통해서는 무한정 깊어지는 노드가 있을 경우 에러가 생길 수 있다는걸 명심하자.

 

2. 스택

인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 

가장 마지막에 넣은 노드들만 꺼내서 탐색하는 방법을 통해 마찬가지로 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]
}
# 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) # 2
        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] 이 출력되어야함