20010
-
[백준]20010: 악덕 영주 혜유 - JAVA문제풀이/백준 2021. 7. 7. 17:08
[백준]20010: 악덕 영주 혜유 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 풀이 🪑 MST를 구하는 활용문제이다. 문제의 조건들을 정리해보자. 마을간 교역로는 양방향이다. 모든 마을은 연결되어있다. 구하는 값은 MST 비용과 MST 내에서 가장 먼 노드간의 거리이다. 🔧 이제 문제 풀이 과정을 생각해 보자. 마을 간 교역로 정보를 입력 받은 후 MST를 구한다. MST를 저장해 둔 다음 MST를 내에서 DFS로 가장 먼 노드간의 거리를 구한다. 가장 먼 노드간의 거리를 구하기 위해선 먼저, 한 정점에..