[💬] 타일 형식중 다중타겟중 이동가능한 가장짧은거 찾아주는 알고리즘 있을까?

[호호호(211.117)]

장애물,길있고그렇다면,

그냥 타겟모두에게 에이스타 한번씩돌려봐서 짧은거 찾는거 최선이겠지?

[익명(ppukku999)]

그럴거 같긴 한데, a* 을 조금 손봐서 여러 목적지를 목표로 두고 가장 적은 비용으로 도달하는 첫번째 목적지만을 찾아낼 수는 있을 것 같음.

[퍅셔미(wvvwvwwvw)]

다중타겟중 제일 짧은거 하나 찾을때는 에이스타보다 단순히 Queue돌리면서 탐색하는게 빠를걸?

[퍅셔미(wvvwvwwvw)]

https://en.wikipedia.org/wiki/Lee_algorithm

[익명(usnned)]

타겟 수에 따라서 많이 다를거같음

[익명(usnned)]

타겟이 많은 편이면 BFS하는게 제일 나을듯?

[익명(223.38)]

다이나믹 프로그래밍(DP탐색) 검색 ㄱㄱ

[익명(223.38)]

갈 수 있는 방향이 단순하게 오른쪽 왼쪽이라 하면, 매 선택의 시간마다 오른쪽으로 간다면 최적이 나올까? 왼쪽으로 가면 최적일까? 하다가 마지막 도착지에 어떤 방법이 가장 빨랐는지 혹은 가장 효율적인지 등을 짜게 해주는 알고리즘 풀이법 중 하나임. 한번 검색해보고 니가 생각하는거랑 맞다고 생각들면 검토해봐