• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    미해결

제가 BFS 길찾기를 이해한 게 맞는지 확인 부탁드립니다

22.03.07 02:02 작성 조회수 278

2

BFS를 이용하여 미로의 최단거리를 구하는 방식이

 

1. 일단 갈 수 있는 좌표(맵의 모든 초록색 점)를 BFS로 탐색해 모두 저장한 다음,

2. 도착점(23, 23)을 기준으로 parent만 따라가면서 플레이어가 이동할 좌표를 _points 리스트에 저장한 후(어차피 역순으로 parent를 찾으면서 가게 되면 막혀있는 길로 갈 필요가 없으므로)

3. _points의 순서를 뒤집어서 시작점부터 출발하게 하면 플레이어가 최단거리로 도착점까지 간다

 

이렇게 이해하는 게 맞을까요?

답변 1

답변을 작성해보세요.

0

네 맞습니다.

김지형님의 프로필

김지형

질문자

2022.03.07

감사합니다! 학교에서 DFS BFS를 배울 땐 그래프 그림만 보고 탐색 순서가 어떻게 되는지만 배웠는데 실제로 코드를 짜보니까 보통 어려운게 아니네요.