[Algorithm]Baekjoon 1647 :: 도시 분할 계획

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 
using namespace std;
 
struct Node
{
    int node1;
    int node2;
    int cost;
};
 
int parents[100001] = { 0 };
 
int FindParent(int node)
{
    if (parents[node] == node)
    {
        return node;
    }
 
    return parents[node] = FindParent(parents[node]);
}
 
bool CompareParents(int node1, int node2)
{
    if (FindParent(node1) == FindParent(node2)) return true;
    else return false;
}
 
void UnionParents(int node1, int node2)
{
    node1 = FindParent(node1);
    node2 = FindParent(node2);
    
    if (node1 < node2)
    {
        parents[node2] = node1;
    }
    else
    {
        parents[node1] = node2;
    }
}
 
bool cmp(const Node& a, const Node& b)
{
    return a.cost < b.cost;
}
 
int n, m;
vector<Node> nodes;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        parents[i] = i;
    }
 
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        
        nodes.push_back({ a,b,c });
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    int answer = 0;
    int maxCost = 0;
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        if (CompareParents(nodes[i].node1, nodes[i].node2) == false)
        {
            answer += nodes[i].cost;    
            maxCost = max(maxCost, nodes[i].cost);
            UnionParents(nodes[i].node1, nodes[i].node2);
            --n;
        }
 
        if (n == 1) break;
    }
 
    cout << answer - maxCost;
}
 
 
 
 

 

문제를 읽자마자 MST가 생각났다. 다만, 두 마을로 분할한다는 점에서 어떻게해야할까 생각하다가, 어차피 양방향간선인 하나의 그래프니까, 가장 비싼가중치 하나만 뚝 자르면 되지않을까? 하고 코드를 작성하고 제출했는데 통과했다.