[코딩테스트] node.js BFS vs Astar

 

내가 기억하기로는 두 알고리즘 모두 옵티멀한 경로를 찾을 수 있다.

Astar는 목적지를 알고 있는 경우에만 사용할 수 있는 대신 BFS보다 훨씬 빠른 것으로 알고 있다. (물론 휴리스틱을 어떻게 설정하느냐에 따라 다르겠지만 일반적으로)

 

https://softeer.ai/practice/7726

위의 소프티어의 문제를 Astar를 써서 풀려고 시도했다.

우선순위큐를 구현하는데 시간이 좀 걸릴 것 같아서 아래와 같이 매 사이클 정렬하여 풀었더니 시간초과가 발생... 

queue = queue.sort((a,b) => a.cost - b.cost);

 

BFS로 푸니까 성공....

그러고보니 지금까지 길찾기 문제 중에 Astar를 쓰는 문제를 한번도 못 봤다.

 

 

여담

js로 코딩테스트를 보면 Astar를 쓰고 싶어도 우선순위 큐를 직접 구현해야함..

그래서 코테는 파이썬이나 C++을 주로 쓰나보다.