codingismylife   1년 전

문제를 보고 최소 스패닝 트리임을 알았지만 처음엔 무조건 스패닝 트리만 만들면 되는 줄 알고 짰다가 틀려서 다시 봤습니다. 

제가 이해한 게 맞나요??

최소 스패닝 트리는 주어진 간선들이 사이클을 이루지 않도록 N개의 노드가 존재하면, N-1개의 간선을 이용하여 모든 N개를 트리로 만드는 것

하지만 문제에서는 2개의 마을로 분할한다고 하였기 때문에, 최소 스패닝 트리를 만들고 간선들 중 길이가 가장 긴 것을 빼버리면, 트리가 2개가 됨은 보장되기 때문에 이렇게 푼다. 

pkearth   1년 전

맞습니다.

codingismylife   1년 전

감사합니다!!

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