Day 64: Python 트리에서 깊이 우선 탐색(DFS), 재귀 없이 깊은 탐색을 위한 스택 기반 반복 순회

Source: Dev.to

Day 64 핵심 정리: 반복 DFS 함수

1. 함수 설계: 스택 및 방문 리스트 초기화

dfs 함수는 트리 딕셔너리와 시작 노드를 받아서 탐색 순서를 반환합니다:

def dfs(tree: dict, start):
    """Perform DFS traversal starting from the given node."""
    visited = []          # store traversal order
    stack = [start]       # stack for DFS (LIFO)

2. 루프 처리: 팝 → 방문 → 자식 역순 푸시

핵심 while‑loop가 스택을 처리합니다:

    while stack:
        node = stack.pop()               # take the top node from stack

        if node not in visited:
            visited.append(node)         # mark node as visited

            # push children in reverse order to maintain left‑to‑right traversal
            for child in reversed(tree.get(node, [])):
                stack.append(child)

    return visited

• 노드를 팝하고 아직 방문하지 않았다면 visited에 추가합니다(전위 순회).
• 자식을 역순으로 푸시하여 가장 왼쪽 자식이 먼저 처리되도록 합니다.
• tree.get(node, [])는 리프 노드도 안전하게 처리합니다.

3. 사용 예시: 트리 정의 및 출력

딕셔너리 기반 트리로 시연합니다:

tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": []
}

start_node = "A"

print("Tree:", tree)
print(f"Starting DFS from node: {start_node}")

traversal = dfs(tree, start_node)
print(f"DFS Traversal Order: {traversal}")

스크립트를 실행하면 트리를 출력하고 A에서 DFS를 시작한 뒤 탐색 순서 [A, B, D, E, C, F]【https://dev.topreorder/】를 보여줍니다.

요약 및 회고

• 스택은 재귀를 시뮬레이션합니다 – 깊은 트리에서도 안전합니다.
• 역순 푸시는 별도 작업 없이 좌‑우 순서를 유지합니다.
• 팝 시점에 방문 처리하면 전위 순서가 됩니다.

재귀 방식은 깔끔하지만 깊이가 > 1000일 경우 실패할 수 있습니다. 반복 방식은 안전하고 제어하기 쉽습니다.

다음 단계 및 참고 자료

• 챌린지 #64 소스 코드: scripts/dfs_tree.py
• 메인 레포지토리: 80-days-of-challenges
• 일일 업데이트: Twitter/X (@Shahrouzlogs)