지금 알고리즘은 먼 길부터 찾고 있는거죠?

Question

안녕하세요. 추석연휴동안 열심히 다시 달리고 있습니다. 들을 때마다 친절하고 머리에 잘 들어오는 강의, 늘 놀라고 있습니다. 감사합니다. 그런데 현재 수업에 나온 길찾기 알고리즘은, 사실은 먼 거리부터 찾고 있는 것 맞나요? 프라이어리티 큐는 팝 하면 가진 것 중에 최대값을 꺼내고, 그 최대값은 F값으로, 먼 길이 예약 될 수록 F값이 클테고, 그래서 팝 하면 h값이 커지는 먼 길 방면부터 확인하게 되는 것 같아요. 맞을까요? 그래서 프라이어리티 큐를 역으로 만들어서 최소값부터 꺼내게 만들어 사용하면, 일단 도착점까지 가까워지는(h가 작은) 방향으로 먼저 길을 찾아봐서, 계산횟수가 줄어들기를 기대할 수 있을까요?

Rookiss · Answer

그런데 현재 수업에 나온 길찾기 알고리즘은, 사실은 먼 거리부터 찾고 있는 것 맞나요? -> 그렇지 않습니다. cost가 최소로 예상되는 지점부터 먼저 찾습니다. [우선순위큐 마무리] 강좌에서 비교 구문을 받을 수 있게 만들어 놨고, PQ를 건드릴 필요 없이 struct PQNode의 CompareTo 조건에 따라 PQ에서 먼저 꺼낼 대상이 정해집니다.