SW Expert Academy 1795 - 인수의 생일 파티

문제 링크

---

-

문제 해결

---

 1. 단방향 그래프를 입력받고, 1부터 N까지의 임의의 점에서 K까지의 최단거리와 K부터 임의의 점까지의 최단거리의 합 중에서 가장 큰 값을 구하는 문제.

 2. 다익스트라 알고리즘으로 문제 해결.

주의할 점 || 생각해볼 점

---

 1. 최대 간선의 수(N)가 10,000개, 최대 정점의 수(M)가 1,000개. 1부터 N까지의 임의의 수 전부에서 최단거리를 구하려면 시간복잡도 에 의해서 아슬아슬해진다. 그러므로 입력 받을 때, 정방향과 반대방향 인접리스트를 두 개 만들어서 K에서 다익스트라 알고리즘을 두 번 수행하면 된다.

 

참고

---

 - 다익스트라 알고리즘 visual code : https://www.swexpertacademy.com/main/visualcode/main.do#/home/mainlayout

※ 정확하고 부드러운 태클은 언제나 환영입니다.