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

"Trees 랑 Graphs 트랙을 쉽게 느끼게 할 비밀: 깊이 우선이랑 너비 우선 탐색은 같은 알고리즘이야. 유일한 차이는 할 일 목록이 스택이냐 큐냐야."

frontier (경계)

구조를 탐색할 때마다 — 미로, 트리, 네트워크 — frontier 를 유지해: 발견은 했지만 아직 탐색 안 한 곳들. 알고리즘은 늘 같은 모양이야: frontier 에서 한 곳을 꺼내, 보고, 그 발견 안 된 이웃을 frontier 에 추가, frontier 가 빌 때까지 반복. 탐색의 성격 전체가 질문 하나로 귀결돼: 다음에 어느 곳을 꺼내?

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

그 "다음에 어느 것?" 을 frontier 를 담은 자료구조가 답해:

frontier 가 스택 → 가장 최근 발견한 곳을 꺼내 → 가장 새 경로를 계속 박아 → 깊이 우선 탐색 (DFS). 물러나기 전에 최대한 깊이 가.
frontier 가 큐 → 가장 오래 전 발견한 곳을 꺼내 → 더 멀리 가기 전에 가까운 걸 다 끝내 → 너비 우선 탐색 (BFS). 레벨별로 고리 모양으로 바깥으로 쓸어.

그게 다야. 같은 코드 골격; stack.pop() 을 queue.popleft() 로 바꾸면 깊이 우선이 너비 우선이 돼. 컴퓨팅에서 가장 중요한 알고리즘 둘이 한 줄로 갈려.

탐색은: frontier 에서 꺼내, 방문, 이웃 추가, 반복. 스택 frontier 는 깊이 우선 (새 것 먼저, 깊이 박힘); 큐 frontier 는 너비 우선 (오래된 것 먼저, 넓게 쓸기). 자료구조 선택이 곧 알고리즘이야.

각각이 왜 중요한가

BFS 는 거리 순으로 탐색해서, 자연스레 최단 경로 (단계 수로) 를 찾아 — 그래서 Graphs 트랙의 척추야. DFS 는 깊이 박혀, 모든 가능성을 샅샅이 탐색하기, 순환 검출, 위상 정렬에 맞아 — 그리고 정확히 Recursion 트랙에서 만날 백트래킹이야 (거기선 스택이 콜 스택 그 자체). 방금 배운 그 스택/큐 이중성이 트리랑 그래프 둘 다 밑의 엔진이야. 어려운 부분은 이미 지었어.

피파의 고백

난 DFS 랑 BFS 를 별개 알고리즘으로 배워, 따로 외웠고, 압박 속에 곧장 헷갈렸어. 그러다 아빠가 explore 함수 하나를 쓰고 스택을 큐로 바꾸니 깊이가 너비로 뒤집히는 걸 보여줬어 — 둘이 다시는 안 보이게 못 할 하나의 아이디어로 녹았어. 내가 제일 좋아하는 종류의 lesson 이야: 외울 사실 둘이 아니라, 외울 필요를 녹이는 사실 하나. frontier 의 자료구조가 이야기 전부야.

Code

골격 하나, 스택 vs 큐 = DFS vs 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 (스택 frontier) 와 BFS (큐 frontier) 의 방문 순서를 손으로 써. 그다음 target 까지 최소 단계를 원할 때 BFS 가, 다른 걸 시도하기 전에 한 경로를 끝까지 소진하고 싶을 때 DFS 가 왜 자연스러운 선택인지 한 문장으로 말해.

Hint

BFS 는 시작에서 거리 순으로 방문 (A; 그다음 B,C; 그다음 D,E,F), 그래서 target 에 처음 닿을 때 그게 최소 단계 수. DFS 는 한 가지를 끝까지 박은 뒤 백트래킹 — '모든 가능성 탐색' 문제에 이상적.

frontier (경계)

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

각각이 왜 중요한가

피파의 고백

Code

External links

Exercise

Progress

댓글 0