BOJ 14621 - 나만 안되는 연애

문제 링크

---

https://www.acmicpc.net/problem/14621

문제 해결

---

 1. "모든 정점이 연결되어야한다", "도로의 합이 최소가 되어야한다" → 최소신장트리(MST) 문제를 크루스칼 알고리즘(Kruskal Algorithm)으로 해결 

주의할 점 || 생각해볼 점

---

 1. 최소 경로를 해결하는 Dijkstra 알고리즘을 사용할 수 없다. 실제 정점끼리의 최소 거리랑 신장된 트리에서의 거리는 다를 수 있다.

   

 2. 이분 그래프로 해결하려면 까다롭다. 그래서 정점마다 W or M 을 저장해서 서로 같다면 연결에서 제외했다.

 3. 만약 모든 정점이 연결되지 않으면 -1을 출력하는 것을 잊으면 안된다.

참고

---

 - 

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