Priority Queue 대신 LinkedList 사용 이유를 알 수 있을까요??

Question

안녕하세요 강사님! 강의 잘 듣구있습니다. 혹시 제목 그대로 LinkedList 를 사용하신 이유를 알 수 있을까요? 또한, Priority Queue 사용시에는 초기 pq.add(new int[] {x, y, 1}); 이렇게 하면 되는지 문의드립니다!

pushupman · Answer

강준님 안녕하세요 1-1질문주신내용: 혹시 제목 그대로 LinkedList 를 사용하신 이유를 알 수 있을까요? 또한, Priority Queue 사용시에는 초기 pq.add(new int[] {x, y, 1}); 이렇게 하면 되는지 문의드립니다! 1-2 답변 : bfs문제는 queue에 넣어서 한칸씩 이동하는 개념이죠, 일반적으로 Queue q = new LinkedList<>(); 이걸 사용하죠 만약 Priority Queue를 쓰고 싶다면, 내부적으로 우선순위를 만들어줘야겠죠? maxHeap, minHeap 중에 하나로 만들어서 특정한값으로 소팅이 되게해주죠 예를들어 a->b 지점가는데 cost 500, a->c지점 가는데 cost 200 이런 경우 cost를 비교대상으로 잡고 maxHeap, minHeap을 잡죠 이 문제의 경우에는 한칸한칸 이동하는 개념이라 Priority Queue를 사용하지 않았습니다. 추후 Priority Queue 를 다익스트라 최단거리 문제를 다뤄 보도록 하겠습니다. 이해안되시면 추가 질문주세요~ 감사합니다.

jundol · Answer

이해했습니다! 답변 감사합니다~!