Page 19 -

1
● 탐색 결과를 하나하나 메모하면서 실행하면 동적 계획법이 됩니다(5장에서 설명합니다).
● 순서 관계를 정리하는 기법인 위상 정렬(topology sort)을 구현할 수 있습니다(13.9절에서 설
명합니다). 알고리즘이란?
● 네트워크 흐름 알고리즘에서 서브 루틴으로 기능합니다(16장에서 설명합니다).

이 절에서 소개한 깊이 우선 탐색을 그래프 탐색으로 바꿔 생각해 보면 시야가 훨씬 넓어집니다.

그래프 탐색은 13장 이후에 자세히 설명하겠습니다.

1.2.2 미로로 배우는 너비 우선 탐색

그림 1-5의 미로를 통해 너비 우선 탐색(breadth-first search, BFS)을 소개합니다. 스타트(S)에서 골
(G)까지 가고 싶다고 합시다. 한 번 이동할 때 현재 칸에 이웃한 상하좌우 칸으로 이동할 수 있습
니다. 하지만 색칠된 칸으로는 이동할 수 없습니다. S 칸에서 G 칸까지 가장 짧은 횟수로 도달하

려면 몇 번 이동해야 할까요?

그림 1-5 미로 최단 경로 문제

(

ӏ஗

4

이 미로를 너비 우선 탐색으로 푸는 과정이 그림 1-6입니다. 우선 그림 1-6의 왼쪽 위 그림처럼
S 칸에서 한 번 움직이면 갈 수 있는 칸에 1이라는 숫자를 적습니다.

035