A* 알고리즘 질문입니다.

Question

제가 이해한 바는 이동할 때마다 상하좌우 의 점을 갈 때 거리를 비교해서 거리가 가장 짧은 쪽으로 이동한다는 걸로 이해를 했습니다. 그러면 미로가 난잡하게 되어 왼쪽으로 빙 돌아가야 한고 오른쪽으로도 어느정도 길이 뚫려 있지만 최종 점 앞에서 막혀있다고 가정하면 거리 순으로 이동을 하게 되면 왼쪽이 아니라 오른쪽으로 가지 않을까요?  이 부분이 지금 이해가 어려워 추가적으로 질문드립니다,

Rookiss · Answer

제가 이해한 바는 이동할 때마다 상하좌우 의 점을 갈 때 거리를 비교해서 거리가 가장 짧은 쪽으로 이동한다는 걸로 이해를 했습니다. -> 그렇지는 않습니다. 가까워 보이는 쪽으로 [먼저 방문해서 검사를 하는 것]은 맞지만 먼저 방문한다고 [최종 이동경로가 반드시 그쪽으로 잡히는 것]은 아닙니다. 오른쪽으로 쭉 방문하다가 더 이상 길이 없음을 알고  다시 왼쪽으로 서칭을 하게 될 것이며, 결과적으로 어떤 최단 경로를 타고 목적지까지 왔는지를 꾸준히 기록하기에 모든 방문이 끝난 뒤에는 최단경로 결과만 추출할 수 있습니다.