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

안녕하세요 유태님 ㅎㅎ

입력 값을 u, v, w 순서대로 입력을 하였는데 adj배열과 우선순위 큐의 입력을 w, v 순서대로 하셨더라구요. 이걸 v, w 순서대로 입력을 바꾸면 시간초과가 납니다.

-> 이건 우선순위큐에 넣는 pair라서 순서가 중요합니다. pair는 first, second 순으로 정렬이 되는데요. 여기서 first가 비용이죠?

다익스트라에서 비용을 먼저 정렬하고 -> 노드 형태로 정렬해야 하기 때문에 순서를 바꾸면 안됩니다. 만약 순서를 바꿀 경우 pair를 쓰지 않고 구조체를 써서 정렬 우선순위를 설정해주어야 합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 한유태님 반갑습니다!

다익스트라 알고리즘은 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. adj 배열과 우선순위 큐에 데이터를 잘못 넣으면 당연히 올바른 동작을 하지 않거나 성능이 저하될 수 있습니다.

일반적으로 adj 배열과 우선순위 큐에 (비용, 노드)의 형태로 데이터를 넣는 이유는 우선순위 큐가 비용이 낮은 것부터 처리하도록 하기 위함입니다. 만약 (노드, 비용) 형태로 잘못 넣었다면, 우선순위 큐가 올바르게 작동하지 않아 시간초과가 발생할 수 있습니다.

다음은 유사 질문을 다루고 있는 페이지 링크입니다: 다익스트라 알고리즘 이해 및 적용 방법.

간단히 요약하자면:

1. 우선순위 큐: 비용(길이)을 기준으로 정렬하기 위해 (비용, 노드) 형태로 입력해야 효율적입니다.
   
2. 역방향 입력 조심: 코드 상에서 어떤 행위가 우선되어야 하는지 잘 파악해야 하고, 우선순위 큐의 핵심을 이해해야 합니다.
   

혹시 코드 내에 변수명이 혼동이 있을 수 있으니, 코드 흐름을 다시 한번 점검해 보시고, 비용과 노드의 처리 순서가 바르게 설정되어 있는지 꼭 확인해 보세요. 그래도 문제가 해결되지 않는다면, 강사님께 문의하셔서 전문적인 조언을 받으시는 것도 좋은 방법일 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.