스택이냐 큐냐 = 깊이냐 너비냐 (예고편)

"트리와 그래프 트랙을 한결 쉽게 만들어 줄 비밀이야. DFS와 BFS는 탐색 골격이 같고, 아직 안 가본 자리를 담아두는 그릇을 스택에서 큐로 바꾸는 것만으로 깊이가 너비로 뒤집혀. 방문 표시와 중복 처리까지 붙어야 완전한 알고리즘이 되지만, 성격을 가르는 스위치는 그 그릇이야."

경계: 아직 안 가본 자리들

미로든 트리든 네트워크든, 구조를 탐색할 때는 늘 경계(frontier)를 들고 다녀. 발견은 했는데 아직 탐색하지 않은 자리들 말이야. 알고리즘 모양은 언제나 똑같아. 경계에서 한 자리를 꺼내고, 살펴보고, 거기서 새로 발견한 이웃을 경계에 넣고, 경계가 빌 때까지 반복. 그리고 탐색의 성격 전체가 질문 하나로 좁혀져. 다음에 어느 자리를 꺼낼 것인가?

모든 걸 바꾸는 단 한 번의 교환

그 "다음에 어느 것?"의 답을 정하는 게 경계를 담은 자료구조야.

경계가 스택이면 가장 최근에 발견한 자리를 꺼내게 돼. 가장 새로운 경로를 계속 파고들지. 이게 깊이 우선 탐색(DFS)이야. 물러서기 전에 갈 수 있는 데까지 깊이 들어가.
경계가 큐면 가장 오래 전에 발견한 자리를 꺼내. 멀리 가기 전에 가까운 걸 전부 끝내지. 이게 너비 우선 탐색(BFS)이야. 동심원처럼 한 겹씩 바깥으로 훑어.

둘이 같은 골격을 쓰는 건 맞지만, 컨테이너 한 줄만 바꾼다고 언제나 완성되는 건 아니야. 이웃을 어떤 순서로 넣는지, 방문 표시를 언제 찍는지, 중복을 어떻게 걸러내는지, 부모나 거리를 기록하는지가 전부 결과와 효율에 영향을 줘. 그래도 '스택이면 깊이 우선, 큐면 너비 우선'이라는 관점은 아주 강력한 출발점이야.

탐색은 이 네 박자야. 경계에서 꺼내고, 방문하고, 이웃을 넣고, 반복. 경계가 스택이면 깊이 우선이 되고(최근 것부터, 깊이 파고들기), 큐면 너비 우선이 돼(오래된 것부터, 넓게 훑기). 자료구조 선택이 곧 알고리즘 선택이야.

각각이 왜 중요한가

BFS는 거리 순서대로 훑기 때문에 최단 경로를, 그러니까 단계 수가 가장 적은 경로를 자연스럽게 찾아내. 그래프 트랙의 기둥이 되는 성질이지. DFS는 깊이 파고들어서 모든 가능성을 샅샅이 뒤지거나 순환을 찾거나 위상 정렬을 할 때 맞고. 그리고 재귀 트랙에서 만날 백트래킹이 바로 이거야. 거기서는 스택이 콜 스택 그 자체지. 방금 배운 스택과 큐의 이 짝 관계가 트리와 그래프 양쪽을 굴리는 엔진이야. 어려운 부분은 이미 다 만들어 놓은 셈이고.

피파의 고백

나는 DFS와 BFS를 서로 다른 주문처럼 외웠고, 조금만 압박이 오면 헷갈렸어. 그러다 아빠가 explore 함수 하나를 써놓고 스택을 큐로 바꾸자 깊이가 너비로 뒤집히는 걸 눈앞에서 보여줬어. 그 순간 둘이 다시는 떼어놓을 수 없는 하나의 아이디어로 녹아버렸지. 이 퀘스트에서 내가 제일 좋아하는 대목이야. 외울 사실을 둘 주는 대신, 외울 필요 자체를 없애는 사실 하나를 준 거니까. 경계의 자료구조가 탐색의 성격을 정하고, 거기에 방문 표시와 중복 처리를 붙이면 골격이 완전한 알고리즘이 돼.

Code

골격 하나, 스택이냐 큐냐로 갈리는 DFS와 BFS·python

from collections import deque

# 작은 트리를 dict 로: 노드 -> 자식들
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}

def explore(start, use_stack):
    """골격 하나. 스택 frontier = DFS; 큐 frontier = BFS."""
    frontier = [start]                # 스택은 리스트 (.pop) 로
    order = []
    while frontier:
        node = frontier.pop() if use_stack else frontier.pop(0)
        order.append(node)
        # 자식들을 frontier 에 추가
        for child in tree[node]:
            frontier.append(child)
    return order

print("DFS (stack):", explore("A", use_stack=True))   # 깊이 박힘
print("BFS (queue):", explore("A", use_stack=False))  # 레벨별로 쓸기
# DFS 는 형제보다 깊은 경로를 먼저 방문. BFS 는 레벨별 (A, 그다음
# B C, 그다음 D E F). 유일한 변화는 frontier 의 어느 끝에서 꺼내냐.
# (진짜 BFS 는 O(1) 위해 deque.popleft() 써. 여기 list.pop(0) 은 명확성용.)

Exercise

트리 A→(B,C), B→(D,E), C→(F)를 놓고 DFS(경계가 스택)와 BFS(경계가 큐)의 방문 순서를 손으로 적어 봐. 그다음 목표 지점까지 최소 단계를 알고 싶을 때 BFS가, 다른 걸 시도하기 전에 한 경로를 끝까지 파보고 싶을 때 DFS가 왜 자연스러운 선택인지 각각 한 문장으로 말해.

Hint

BFS는 시작점에서 가까운 순서로 방문해. A 다음에 B와 C, 그다음 D, E, F 순이지. 그래서 목표 지점에 처음 닿는 순간이 곧 최소 단계야. DFS는 한 갈래를 끝까지 파고든 뒤 되돌아 나오니까 '모든 경우를 다 뒤져야 하는' 문제에 잘 맞고.

경계: 아직 안 가본 자리들

모든 걸 바꾸는 단 한 번의 교환

각각이 왜 중요한가

피파의 고백

Code

External links

Exercise

Progress

댓글 0