6.3.2 깊이 우선 탐색: 한 방향으로 쭉 따라 여행하기

깊이 우선 탐색(DFS)은 스택을 사용합니다. 그런데 조금 후 코드를 살펴보면 스택은 보이지 않고 재귀 함수를 호출하는 형태로 구현되어 있습니다. 둘 사이의 연관성을 눈치챘나요? 함수 실행 중 다른 함수를 호출하면 스택 프레임이 쌓입니다. 스택 프레임이 바로 스택입니다. 재귀 함수를 호출한다는 것은 스택 프레임을 요소로 스택에 쌓는 것과 같죠. 물론 우리가 구현했던 스택 자료 구조와 반복문을 이용해서 구현할 수도 있습니다. 이 절에서는 먼저 스택 프레임을 이용하여 묵시적으로 스택을 사용하는 경우와 스택 자료 구조를 명시적으로 사용하는 경우를 모두 살펴보겠습니다. 먼저 재귀 함수를 사용해서 구현하는 코드를 보겠습니다.

코드 6-8

    def __dfs_recursion(self, v):
        # 방문
        print(v, end=" ")
        # 방문 체크
        self.visited[v] = True

        adj_v = self.adj_list[v]
        for u in adj_v:
            if not self.visited[u]:
                self.__dfs_recursion(u)

    def dfs(self, v):
        self.init_visited()
        self.__dfs_recursion(v)