똑똑한 코드 작성을 위한 실전 알고리즘

244

똑똑한 코드 작성을 위한 실전 알고리즘

➐

v

와 인접하고 방문 처리되지 않은 각 노드

w

에 대해, 탐색이

v

에서 와서

w

에 도달함을 기억한다.

➑

맨해튼 거리의 음숫값을 우선순위로 해 우선순위 큐의 알맞은 위치에

w

를 넣고 여러 번 방문하지 않도록 방문 처리

한다.

➒

src

에서 시작된 탐색의 이전 노드

v

를 각각 기록한 탐색의 구조를 반환한다.

유도 탐색이 똑똑한 이유는 두 노드 간의 맨해튼 거리를 계산하는

distance

_

to

()

함수에 있다.

유도 탐색은 최단 경로를 찾는다는 보장이 없고 검색을 유도하기 위한 단일 목적지를 미리 가

정했으므로 너비 우선 탐색보다 성능이 좋지 않다. 너비 우선 탐색은 시작 노드에서 목적지 노

드뿐 아니라 접근 가능한 모든 노드까지의 최단 경로를 확인할 수 있다. 하지만 이 과정에서 너

비 우선 탐색은 더 많은 노드를 탐색하는데, 유도 탐색을 사용하면 미로 그래프에서 불필요한

탐색을 줄일 수 있다. [그림

7

-

8

]은 같은 미로로 앞서 소개한 세 가지 탐색 알고리즘을 나란히

비교한 것이다.

그림

7-8

너비 우선 탐색, 깊이 우선 탐색, 유도 탐색 비교

너비 우선 탐색은 알고리즘 특징에 따라 거의 모든 노드를 탐색한다. 최단 경로를 찾기 위한 깊

이 우선 탐색은 제대로 된 방향을 추적하기 위해 가능성이 별로 없어도 방향을 반복해서 ...