Page 20 -

그림 1-6 너비 우선 탐색 동작 개념도

( (

4 4

( (

4 4

이어서 그림 1-6의 오른쪽 위 그림처럼 1이 적힌 칸에서 다시 한 번 움직이면 갈 수 있는 칸에 2

라고 적습니다. 이건 스타트(S)에서 두 번 움직이면 갈 수 있는 칸입니다. 이어서 그림 1-6의 왼
쪽 아래처럼 2라고 적힌 칸에서 한 번 움직이면 갈 수 있는 칸에 3이라 적고, 이걸 반복하면 최종
적으로 그림 1-6의 오른쪽 아래처럼 G 칸은 16이 됩니다. S에서 G에 도착하는 최단 경로 길이가

16이라는 뜻입니다. 이 과정을 사용해 G 칸뿐만 아니라 다른 칸도 S 칸에서 시작해 도달하는 최
단 경로를 구할 수 있습니다.
이렇듯 너비 우선 탐색은 출발점에서 가까운 곳부터 순서대로 탐색하는 탐색 알고리즘입니다. 출

발점에서 한 번에 갈 수 있는 곳을 우선 탐색해서 더 이상 없으면 두 번에 갈 수 있는 곳을 탐색하
고, 다시 세 번에 갈 수 있는 곳을 탐색하며, 이 과정을 안 간 곳이 없을 때까지 반복합니다. 너비
우선 탐색도 깊이 우선 탐색처럼 단순 무식한 탐색 알고리즘이지만, 목표를 달성하는 최소 절차를

알고 싶은 경우에 유용합니다. 마찬가지로 너비 우선 탐색도 깊이 우선 탐색처럼 그래프 탐색으로
바꿔 생각해 볼 수 있습니다. 이에 대한 내용은 13장 이후에 자세히 설명하겠습니다.

1.3 알고리즘 예제(2): 매칭 A LG O RI T HM & D AT A S TR U CT UR E S

현대 사회에서는 매칭(matching)이라는 용어를 많은 곳에서 사용합니다. 매칭을 가지고 다음 문제

036