인프런 커뮤니티 질문&답변
작성한 질문수
shortest_path에 대해 질문드립니다.
작성
·
238
답변 2
0
안녕하세요^^
다익스트라와 크루스칼은 조금 차이가 있습니다.
다익스트라 알고리즘은 그래프의 한 정점에서 다른 모든 정점으로의 최단거리 또는 최소비용을 구하는 알고리즘 이고, 그루스칼은 그래프에서 모든 정점이 연결되어 있는 최소비용의 트리를 찾는 알고리즘입니다.
문제에서 힌트라기 보다는 출발지와 도착지가 주어지고 출발지에서 도착지로 가는 최소비용을 구하라고 하면 다익스트라로 판단하고, 그래프가 주어지고 모든 정점이 연결되기 위한 최소비용을 물어보면 크루스칼을 쓰는 정도로만 알고 있으면 됩니다. 그리고 실제 관련된 많은 문제를 풀어보면서 경험으로 얻는 것도 많습니다.
0
안녕하세요, 인프런 AI 인턴이에요.
shortest path는 가장 짧은 경로를 찾는 문제입니다.
다익스트라 알고리즘과 크루스칼 알고리즘은 모두 shortest path 문제를 해결하는 알고리즘 중 하나입니다.
하지만 다익스트라 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 문제에 특화되어 있고, 크루스칼 알고리즘은 최소 신장 트리를 구하는 문제에 특화되어 있습니다.
따라서 둘 중에 어떤 알고리즘을 사용해야 할지는 문제의 조건에 따라 다릅니다.
문제에서 힌트를 제공하는 경우도 있겠지만, 그렇지 않은 경우는 다양한 알고리즘을 생각해보면서 어떤 알고리즘이 문제를 가장 효율적으로 해결할 수 있는지 생각해보시면 됩니다.
추가적으로, 이전 질문이나 관련 자료를 검색하여 참고하시는 것도 좋은 방법입니다.
자세한 설명은 지식공유자에게 문의해보시면 더욱 상세한 답변을 받을 수 있을 것 같습니다.
좋은 학습 되시길 바랍니다. 감사합니다.