크루스칼
-
[백준 BOJ/C++] 1774 우주신과의 교감알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:48
1774번: 우주신과의 교감 크루스칼 알고리즘을 연습해보기 좋은 문제다. 특별히 복잡하게 꼬아놓은 부분은 없는데 사전에 일부 간선만 주어지고 나머지 가능한 모든 간선을 추가하는 과정만 추가되었다. 입력으로 주어지는 모든 노드들 사이에 가능한 모든 간선들을 list up 하고 각 간선의 길이를 계산해두고 이를 토대로 크루스칼 알고리즘을 이용해 최소 신장 트리를 찾아주면 된다. 단, 입력으로 주어지는 이미 연결된 통로는 최소 신장 트리에 반드시 포함되어야 하며 새로 추가한 간선들의 길이의 합을 출력해야 한다. 문제의 포인트 최소 신장 트리를 구할 수 있는가? 간선의 길이는 주어지지 않는다. 최소 신장 트리 사이클 없이 모든 노드를 연결하는 최소 신장 트리 (MST, Minimum Spanning Tree)만..