kdhsong   1년 전

문제에서 가중치의 합이 제일 작은걸 찾아라고했는데,

4 5

2 4 1

6 4 -2

7 4 -8

7 6 -3

6 2 -88


이렇게 들어가면 -101 이 출력되야 최소인거같은데 왜 -96인지모르겠네요.

선을 가장 작게 그리면서 최소를 구하는건가요?

Acka   1년 전

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

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


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

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

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


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

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

Acka   1년 전

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

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


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

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

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

kdhsong   1년 전

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

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

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


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

Acka   1년 전

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

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


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

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

로 바꿔서 입력했습니다.

Acka   1년 전

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

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

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

kdhsong   1년 전

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

댓글을 작성하려면 로그인해야 합니다.