인프런 커뮤니티 질문&답변

강준님 안녕하세요

1-1질문주신내용:

혹시 제목 그대로 LinkedList 를 사용하신 이유를 알 수 있을까요?

또한,  Priority Queue 사용시에는 초기 pq.add(new int[] {x, y, 1}); 이렇게 하면 되는지 문의드립니다!

1-2 답변 :

bfs문제는 queue에 넣어서 한칸씩 이동하는 개념이죠, 일반적으로 

Queue<int[]> q = new LinkedList<>(); 이걸 사용하죠

만약 Priority Queue를 쓰고 싶다면,  내부적으로 우선순위를 만들어줘야겠죠?

maxHeap, minHeap 중에 하나로 만들어서 특정한값으로 소팅이 되게해주죠

예를들어 a->b 지점가는데 cost 500, a->c지점 가는데 cost 200 

이런 경우 cost를 비교대상으로 잡고 maxHeap, minHeap을 잡죠

이 문제의 경우에는 한칸한칸 이동하는 개념이라 Priority Queue를 사용하지 않았습니다.

추후 Priority Queue 를 다익스트라 최단거리 문제를 다뤄 보도록 하겠습니다.

이해안되시면 추가 질문주세요~

감사합니다.

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