문제 링크 : https://www.acmicpc.net/problem/1647
문제 설명
이 문제는 집 N개의 최소신장트리를 구한 이후, 2개로 쪼갰을때 두 신장트리의 가중치 합이 최소가 되는 경우를 구하는 문제이다.
한개의 최소 신장트리를 두개로 쪼개는 방법은, 간선 한개를 지워버리면 2개의 신장트리가 생기게된다. 이 문제는 2개로 쪼개진 MST의 간선 가중치 합이 최소가 되는 경우를 찾는 문제이므로, 지울 간선은 가중치가 가장 큰 간선을 선택하여 지우면 된다.
참고로 나는 프림 알고리즘(Prim's Algoritm)을 이용하여 풀었다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <iostream> #include <vector> #include <queue> using namespace std; int maxi; // 가중치 가장 높은 간선의 가중치 vector<pair<int,int> > map[100001]; bool bmap[100001]; priority_queue<pair<int ,int> , vector<pair<int,int> >, greater<pair<int,int> > >pq; int sum = 0; void prim(int a) // 프림 { bmap[a] = true; for(int i = 0; i < map[a].size(); i++) { if(!bmap[map[a][i].second]) { pq.push(make_pair(map[a][i].first,map[a][i].second)); } } while(!pq.empty()) { pair<int,int>pai = pq.top(); pq.pop(); if(!bmap[pai.second]) { maxi = max(maxi,pai.first); // 가중치가 가장 큰 간선 구하기 sum +=pai.first; // 가중치 합 구하기 prim(pai.second); return; } } } int main() { int a, b; cin >> a >> b; for (int i = 1; i <= b; i++) // 간선 연결 { int c,d,f; cin >> c >> d >> f; map[c].push_back(make_pair(f,d)); map[d].push_back(make_pair(f,c)); } prim(1); cout << sum - maxi; } | cs |
이 문제를 풀고 느낀점
개인적으로 이 문제 이해하는데 너무 오래걸렷다..... 그래서 이 문제를 풀고나서 느낀점은 내가 실제로 코딩테스트를 응시할 때, 문제 자체를 이해하기 힘든 상황이 이번 문제풀때와 같이 연출되지 않도록, 많은 문제를 풀며, 여러 유형의 문제에 대비해야겠다!
