[알고리즘] DFS 개념 설명 및 구현 - python

 

DFS가 머릿속으로는 이해가 되는데, 실제 구현하는 과정에서 완벽히 정리가 되지 않은 것 같아 정리를 해보려 한다.

모든 과정을 하나하나 설명할테니 다른 분들께 도움이 되길 바랍니다.

 

DFS (Depth-First Search) 의 개념

 

'깊이 우선 탐색(DFS)'는 단어 그대로 깊이를 우선적으로 하여 탐색한다는 것으로,

가장 깊은 노드까지 탐색 후 옆으로 이동하여 탐색을 진행하는 것이다.

Root 노드부터 시작하여 그래프의 모든 노드를 방문한다.

 

어디서 사용되는가?

위에서 말했듯 그래프의 모든 노드를 방문해야 할 때 사용한다.

대표적으로는

• 미로 찾기
• 그래프의 위상 정렬
• 전체 탐색(모든 경우의 수)
• 연결 구성 요소 찾기
• 이분 그래프

의 문제를 풀 때 사용된다.

 

구현 방법

stack 과 재귀함수 를 사용하여 구현한다.

 

과정

그림으로 자세히 설명해보자.

우선 루트 노드인 1 부터 탐색을 시작한다.

스택에 1을 넣고 1과 연결된 노드 중 방문하지 않은 노드를 탐색한다.

다음 방문하지 않은 노드 2를 스택에 넣어준다. 그리고 다시 탐색한다.

노드 3도 스택에 넣어준다.

노드 3과 연결된 노드 중에 방문하지 않은 노드는 없으므로 탐색이 종료되었다. 

노드 3을 스택에서 뺀다.

마찬가지로 노드2 또한 탐색이 종료 되었고, 스택에서 빼도록 하자.

이제 다시 루트 노드로 돌아왔고, 루트 노드와 연결된 노드 2, 4, 8 중에서 방문하지 않은 4를 스택에 넣어준다.

위에서 설명한 과정대로 노드6까지 스택에 넣어주도록 하자.

다시 방문했던 노드들은 스택에서 빼주도록 한다.

아직 방문하지 않았던 노드 7을 스택에 넣어준다. 이제 탐색이 끝났으므로 노드 7과 노드 4를 스택에서 뺴준다.

 노드 1과 연결된 마지막 노드 8을 스택에 넣어주고 다음 노드를 탐색한다.

이제 모든 노드를 방문했다. 따라서 모든 노드를 스택에서 제거해 탐색을 완전히 종료한다.

지금까지 DFS를 그래프와 스택을 그려가며 설명해 보았다.

이제 실제 코드로 구현해 보는 연습을 하자.

 

Code

myGraph = {
    'A': ['C'],
    'B': ['D', 'E'],
    'C': ['A', 'F'],
    'D': ['B', 'F', 'G'],
    'E': ['B', 'J'],
    'F': ['C', 'D', 'H'],
    'G': ['D'],
    'H': ['F', 'I'],
    'I': ['H'],
    'J': ['E']
}

위 그래프를 그림으로 표현해 보자.

Stack을 사용하여 DFS를 구현해보자.

def dfs(graph, start_node):
    visited = list() # 탐색이 끝난 노드
    stack = list() # 탐색 중인 노드

    stack.append(start_node) # Root 노드부터 탐색 시작

    while stack: # 탐색이 끝날 때까지
        node = stack.pop() # 탐색이 종료된 노드를 하나씩 꺼낸다.

        if node not in visited: # 탐색이 완료되지 않았다면
            visited.append(node) # 노드를 visited 배열에 추가
            stack.extend(graph[node]) # 해당 노드와 연결된 노드들 추가

    print("DFS = ", visited)
    return visited

dfs(myGraph, 'F')

현재 탐색이 오른쪽부터 순회하였다.

위의 코드에서 reversed(graph[node])로 변경해 준다면 원래의 결과를 얻을 수 있다.

 

재귀함수를 이용해 DFS를 구현해보자.

visited = []
def dfs_recursive(graph, start):
    #이미 탐색이 끝난 노드라면 탐색 종료
    if start in visited:
        return
    
    visited.append(start) # 방문 표시


    for now in graph[start]: # 인접 노드들에 대해 재귀 호출
        dfs_recursive(myGraph, now)

같은 결과를 도출하는 것을 확인 할 수있다. 

 

다음에는 BFS에 대해 알아보도록 하자.