Page 17 -

1.2 알고리즘 예제(1): 깊이 우선 탐색과 1
A LG O RI T HM & D AT A S TR U CT UR E S

너비 우선 탐색 알고리즘이란?

앞으로 여러 문제를 제시하고 문제를 풀기 위한 알고리즘을 살펴볼 텐데, 우선 몇몇 알고리즘을
간단히 설명하겠습니다. 다양한 알고리즘의 기초가 되는 ‘탐색’부터 시작합시다.

1.2.1 빈 칸 채우기 퍼즐로 배우는 깊이 우선 탐색

그림 1-3과 같은 빈 칸 채우기 퍼즐로 깊이 우선 탐색(depth-first search, DFS)을 배워 봅시다. 빈 칸
1
채우기 퍼즐은 계산식이 성립하도록 네모 칸에 0에서 9 사이의 숫자를 채우는 퍼즐입니다. 단,
각 줄 처음에 있는 네모 칸에는 0을 넣으면 안 됩니다.

그림 1-3 빈 칸 채우기 퍼즐

깊이 우선 탐색은 무수한 선택지 중에서 무작정 값을 정해 풀어 보는 행위를 반복합니다. 하다가
막히면 한 단계 돌아가서 다른 선택지를 확인해 봅니다. 그림 1-3 왼쪽 퍼즐을 깊이 우선 탐색으
로 풀어 보면 그림 1-4와 같습니다. 우선 오른쪽 위 칸에 1을 넣어 봅니다. 그리고 그 아래 칸도
1이라고 가정합니다. 하지만 그림 1-4처럼 파란색 3과 모순됩니다. 모순을 발견하면 한 단계 되
돌아가서 다음 숫자를 시험해 봅니다. 이러한 탐색을 반복하는 것입니다.

1 빈 칸 채우기 퍼즐은 보통 답이 딱 하나만 있도록 만듭니다.

033