• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    미해결

최단 경로 판단에 대하여

21.04.03 17:19 작성 조회수 160

0

BFS가 최단 경로를 찾는데 사용된다고 하셨는데 어떻게 최단 경로를 파악하는지 따라 해보았지만 잘 모르겠습니다.

강의에서 길 찾는 맵을 생성하는 것은 항상 경로가 한 길밖에 없어서 그 길로만 다니는게 아닌가라는 생각이 듭니다 

이전 강의에서는 distance[start] 를 사용하여 이동하는데 소모되는 값을 구하기는 했지만 이번 길 찾기에서는 그런 것을 사용하지 않고 최단경로로 간다고 하시는데 이 부분이 이해가 가지않습니다.

[ 예를들어]

만약, 목적지까지 갈 수 있는 길이 2개가 있고, 1번째 길은 15걸음  2번째 길은 14걸음이 필요하다고 할 때 ,이번 수업에서 사용한 코드에서 둘 중 어떤것을 최단 경로라고 판단하는지 이해가 되지 않습니다.(비교구문을 사용하지 않아도 가능한것 인지도 궁금합니다)

코드를 보면서도 우선순위를 결정하는 코드를 못찾겠습니다. 제가 공부가 부족해서 안보이는것 일 수 있겠지만요...

답변 2

·

답변을 작성해보세요.

1

먼저 찾는 길이 가장 빠른 길입니다.
BFS는 한발짝 한발짝, 시작점부터 가장 가까운 점
순서대로 서칭하기 때문입니다. (그래서 '너비' 우선 탐색이죠)
그림을 그려보면서 BFS가 찾는 순서를
손으로 그려보시기 바랍니다.

0

윤동근님의 프로필

윤동근

질문자

2021.04.03

감사합니다 선생님