최소 스패닝 트리(Minimum Spanning Tree)란

어떤 그래프의 모든 정점을 연결하는 부분 그래프 중 그 합이 최소가 되는 트리를 말한다고 되어있는데,

'트리'이므로 사이클이 없는 간선들로 이루어집니다.

같은 말로 V개의 정점이 있으면 스패닝 트리는 모든 정점을 포함하는 V-1개의 간선으로 구성되죠.

MST는 그런 스패닝 트리 중에 간선의 총합이 가장 작은 것을 말합니다.

https://en.wikipedia.org/wiki/Minimum_spanning_tre...

그림을 보시면 좀 더 이해가 쉬우실거예요 :)

-101이면 아마 -88, -8, -3, -2 간선을 선택하신 것 같은데

적으신 예시는 (2), (4), (6), (7) 네 개의 정점이 있는 그래프 맞죠?

제가 맞게 그린거라면 -2 간선에 해당하는 (4)는 -8 간선에, (6)은 -3 간선에 의해 이미 커버되고 있으므로

-2 간선을 추가하면 사이클이 생기지 않나요?

이미 -88, -8, -3, 세 개의 간선이 선택되었으므로 스패닝 트리가 완성됐기도 했구요

아 네 -101 이 아니라 -99가 답인거같은데 ...

맞은소스코드에서는 -96이 답이더라구요 ..

왜 -3을 빼먹는지모르겠어서요 ㅠ

문제에 간선의 수가 최소가 되게하라는 말도없는데 ㅠ

방금 AC받은 코드로 돌려보니

위 케이스의 답은 -99가 맞아요,

정점의 번호가 1 ~ V인듯 하길래

(2) -> (1) / (4) -> (2) / (6) -> (3) / (7) -> (4)

로 바꿔서 입력했습니다.

주신대로 입력하면 -96이 나오네요.

아마 1 ~ V 까지의 정점만 포함하게 하는 코드인데

그 이외의 정점들이 섞여서 그런 것 같아요.

아 1 ~ V 까지면 그렇게되네요. 너무너무감사합니다 Acka님!