그래프 (1) - 깊이우선탐색 (DFS, Depth First Search)

정점 (vertex) 와 엣지 (edge) 로 구성된 그래프에서 그래프의 각 정점을 방문하는 그래프 순회에는 깊이우선탐색 (DFS, Depth First Search) 와 너비우선탐색 (BFS, Breadth First Search) 가 있습니다. 

이번 포스트에서 살펴볼 그래프 순회 방법은 깊이우선탐색으로 19세기 프랑스의 수학자 찰스 피에르 트레모 (Charles Pierre Tremaux) 가 미로 찾기 문제를 풀다가 고안한 것으로 알려져 있습니다.

깊이우선탐색은 보통 1. 스택, 2. 재귀 로 구현할 수 있으며 코딩 테스트때 그래프 관련 단골 문제로 출제되는 만큼 굉장히 중요한 문제입니다. 먼저 다음 그림과 같은 그래프를 구성해 보겠습니다.

위 그래프에 대해서 각 정점 별 이웃을 담은 인접 리스트를 딕셔너리 형태로 표현해 보겠습니다.

graph = {1: [2,3,4], 2: [5], 3: [5], 4: [], 5: [6,7], 6: [], 7: [3] }

그러면 정점 1부터 그래프 전체를 깊이우선탐색은 어떻게 순회하는지 스택, 재귀 방법으로 각각 살펴보겠습니다.

깊이우선탐색 with 스택

스택은 Last In First Out (LIFO) 자료형인데, 이 특성으로 깊이우선탐색을 어떻게 구현할까요? 파이썬의 리스트 타입은 스택으로 기능하니 리스트를 하나 선언한 후에 정점의 인접 점들을 담고 마지막 원소 (Last In) 에 대해 또 인접 점들을 방문하는 방법이면 가능할 것 같습니다.

파이썬 코드

def dfs_with_stack(start_v): # 시작점 (start_v) 가 들어왔을 때 그래프 탐색 시작
    discovered = [] # 탐색 결과물을 담을 result
    stack = [start_v] # 탐색에 활용할 stack
    while stack:
        vertex = stack.pop() # list의 pop을 활용해 마지막 원소 추출
        ## 기존에 방문했던 vertex가 아니라면 결과에 추가하고 인접점 방문
        if vertex not in discovered:
            discovered.append(vertex)
            
            ## 인접점 방문해서 stack에 추가
            for neighbor_vertex in graph[vertex]:
                stack.append(neighbor_vertex)
            
    return discovered

탐색 순서 (discovered) 는 어떻게 될까요? 먼저 stack에는 1 이후에 인접점인 2,3,4가 담길 것이고 pop에 의해 4가 먼저 discovered에 추가됩니다. 4는 인접점이 없으므로 discovered에 3이 추가되고 3에는 인접점이 5가 있으므로 stack에 5가 담기면서 바로 마지막 원소인 5가 discovered에 추가됩니다. 최종 결과는 다음과 같습니다.

print(dfs_with_stack(1))
=> [1, 4, 3, 5, 7, 6, 2]

 

깊이우선탐색 with 재귀

재귀를 이용한 깊이우선탐색은 스택을 이용한 경우보다 코드가 더 간결해집니다. 방문한 정점에 대해서 같은 함수를 또 호출하면 되겠죠. 코드는 다음과 같습니다.

파이썬 코드

def dfs_with_recursive(start_v, discovered=[]):
    discovered.append(start_v) # 정점 추가
    ## 인접점 방문
    for neighbor_vertex in graph[start_v]:
        ## 방문하지 않은 정점이라면 재귀를 통해 탐색
        if neighbor_vertex not in discovered:
            discovered = dfs_with_recursive(neighbor_vertex, discovered)
          
    return discovered

탐색 순서는 어떻게 될까요? 먼저 1의 인접점인 2,3,4에 대해서 결과에 없는 정점에 대해 재귀함수를 호출합니다. 이번에는 2가 먼저 discovered에 담기겠네요. 그 재귀함수 안에서 2의 인접점인 5에 대해 재귀함수를 또다시 호출합니다. 5에 대해 호출한 재귀함수 안에서는 5의 인접점인 6,7에 대해 각각 재귀함수를 호출하게 되며, 더 이상 인접점이 없는 정점에 대해서는 해당 정점만 추가한 채 return합니다. 최종 결과는 다음과 같습니다.

print(dfs_with_recursive(1))
=> [1,2,5,6,7,3,4]

 

홍머스 정리

• 깊이우선탐색은 스택이나 재귀로 구현 가능
• 해당 정점을 추가하고 그 정점의 인접점에 대해서 깊이 우선적으로 탐색

참조

• <파이썬 알고리즘 인터뷰>, p323-325