[알고리즘] DFS (Depth First Search)

📚 DFS란(Depth First Search)?

 

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

 

DFS는 이름에 나와있는 그대로 끝까지 탐색하는 거에 초점을 맞춥니다.

그래서 그래프의 최대 깊이만큼의 공간을 요구하며, 이는 공간을 적게 쓰는 것입니다.

그러나 최단 경로를 탐색하기는 쉽지 않다. 모든 경로를 탐색하는 것이 아니기 때문입니다.

 

 

📋 DFS 전체 과정

 

DFS의 알고리즘 방식을 설명하면 다음과 같다.

 

 

https://velog.io/@513sojin/C%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80BFS

 

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

 

📝 DFS 코드(feat : python)

 

이를 코드로 구현하려면 자료구조 스택을 사용하시는 것이 편리합니다

스택을 사용하면 방법은 다음과 같습니다.

 

1. 루트 노드를 스택에 넣는다.
2. 현재 스택의 노드를 빼서 visited(또 다른 배열)에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2부터 반복한다.
5. 스택에 아무것도 없으면 탐색을 종료한다.

 

 

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'D', 'E'],
    'C' : ['A', 'F', 'G'],
    'D' : ['B', 'H', 'I'],
    'E' : ['B', 'J'],
    'F' : ['C'],
    'G' : ['C'],
    'H' : ['D'],
    'I' : ['D'],
    'J' : ['E'],
}
visited = []

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

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

    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for value in adjacent_graph[current_node]:
            if value not in visited:
                stack.append(value)

    return visited


print(dfs_stack(graph, 'A'))  # 'A' 이 시작노드입니다!
# ['A', 'C', 'G', 'F', 'B', 'E', 'J', 'D', 'I', 'H'] 이 출력되어야 한다!

 

https://velog.io/@513sojin/C%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80BFS

 

 

스택으로 구현하게 되므로 맨 뒤에서부터 탐색하게 됩니다.

위에 그림상에선 A 다음 B를 탐색하지만

이 코드는 A 다음 B, C 중에 뒤에 있는 C부터 탐색한다는 것입다.

 

C를 탐색하면 스택에는 [B, A, F, G] 가 있으니 G를 탐색하면

[B, A, F, C] 가 돼야 하는데 C는 이미 탐색을 해서 

[B, A, F] 만 됩니다.

이렇게 반복되면 DFS 절차에 맞게 탐색되는 것입니다.