1647번 - 도시 분할 계획
문제를 보고 최소 스패닝 트리임을 알았지만 처음엔 무조건 스패닝 트리만 만들면 되는 줄 알고 짰다가 틀려서 다시 봤습니다.
제가 이해한 게 맞나요??
최소 스패닝 트리는 주어진 간선들이 사이클을 이루지 않도록 N개의 노드가 존재하면, N-1개의 간선을 이용하여 모든 N개를 트리로 만드는 것
하지만 문제에서는 2개의 마을로 분할한다고 하였기 때문에, 최소 스패닝 트리를 만들고 간선들 중 길이가 가장 긴 것을 빼버리면, 트리가 2개가 됨은 보장되기 때문에 이렇게 푼다.
맞습니다.
감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
codingismylife 1년 전 1
문제를 보고 최소 스패닝 트리임을 알았지만 처음엔 무조건 스패닝 트리만 만들면 되는 줄 알고 짰다가 틀려서 다시 봤습니다.
제가 이해한 게 맞나요??
최소 스패닝 트리는 주어진 간선들이 사이클을 이루지 않도록 N개의 노드가 존재하면, N-1개의 간선을 이용하여 모든 N개를 트리로 만드는 것
하지만 문제에서는 2개의 마을로 분할한다고 하였기 때문에, 최소 스패닝 트리를 만들고 간선들 중 길이가 가장 긴 것을 빼버리면, 트리가 2개가 됨은 보장되기 때문에 이렇게 푼다.