이번에 더 배울 것
큐(queue)는 줄 서기입니다. 뒤에 넣고(enqueue) 앞에서 꺼내며(dequeue), 먼저 들어온 것이 먼저 나가므로 FIFO(First In, First Out)라고 합니다. 스택(stack)은 접시 쌓기입니다. 위에 올리고(push) 위에서 꺼내며(pop), 나중에 들어온 것이 먼저 나가므로 LIFO(Last In, First Out)라고 합니다. 두 구조 모두 넣기와 꺼내기를 한 번에 하나씩만 합니다.
그래프 탐색의 뼈대는 같습니다. 꺼낼 후보를 담는 상자에 출발 노드를 넣고, 하나를 꺼내 방문하고, 그 이웃 중 처음 보는 노드를 상자에 넣는 일을 반복합니다. 상자가 큐면 BFS, 스택이면 깊이 우선 순서가 나옵니다. 스택에 이웃을 넣을 때 목록 순서를 뒤집어 올려야 목록의 첫 이웃이 먼저 나온다는 점도 손으로 해 보면 바로 보입니다.
손으로 굴릴 때 가장 흔한 실수는 방문 표시를 빼먹는 것입니다. 무방향 엣지는 양쪽에서 서로를 이웃으로 보므로, 표시 없이 넣으면 같은 노드가 상자에 계속 다시 들어와 탐색이 끝나지 않습니다. 큐 버전에서는 넣을 때 표시하면 노드가 상자에 한 번만 들어갑니다. 스택 버전에서는 꺼낼 때 표시하고 이미 방문한 노드는 건너뛰어야 재귀로 구현한 DFS와 같은 순서가 나옵니다.
작은 예제로 따라가기
나무 모양 그래프 A–B, A–C, B–D, B–E, C–F(이웃은 알파벳 순)에서 큐로 시작하면 [A] → A를 꺼내 B, C를 넣어 [B, C] → B를 꺼내 D, E를 넣어 [C, D, E]가 됩니다.
이어서 C를 꺼내 F를 넣고 [D, E, F]를 차례로 꺼내므로 BFS 순서는 A, B, C, D, E, F입니다.
스택으로 하면(왼쪽이 바닥) [A] → A를 꺼내 C, B 순으로 올려 [C, B] → 맨 위 B를 꺼내 E, D를 올려 [C, E, D] → D, E, C, F 순으로 꺼내므로 DFS 순서는 A, B, D, E, C, F입니다.
상자와 표시 규칙만 바꾸기
같은 나무 모양 그래프에서 상자 종류와 표시 규칙만 바꿀 때 방문 순서가 어떻게 될지 먼저 적어 보세요.
먼저 들어온 노드가 먼저 나오므로 거리 1인 B, C를 모두 처리한 뒤에야 거리 2인 D, E, F로 넘어갑니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.