[BOJ/21924] 도시 건설, c++

🔗 링크

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

21924번: 도시 건설

🤯 한줄 후기

한줄 후기 : 이름 부터 mst 마음이 편해진다.

🤷 문제

👩‍💻 풀이

최소 스패닝 트리(MST) 문제이다.

추가된 문제에 떠있길래 이름이 뭔가 MST 같아서 들어가봤더니 역시 MST 였다.

 

건물을 모두 연결하는 도로를 선택해야 하므로 바로 MST 라는 걸 알 수 있다.

크루스칼 알고리즘을 이용하여 구현하였다.

단, 모든 도시가 연결 되지 않으면 -1을 출력해야하는데, 예제 3에서 알수 있다 싶이

모든 도시가 연결되지 않는다는 건 그래프의 연결요소의 개수가 1개보다 많다는 이야기다.

따라서 먼저 연결 요소의 개수를 구하기 위해 dfs 탐색을 진행하였다.

dfs 를 1번 건물에서 시작하여 탐색한 후, 방문하지 않은 건물이 있다면 모든 도시가 연결 될 수 없는 것으로 판단한다.

 

dfs 탐색 후 모든 건물이 방문 가능하다면, 바로 크루스칼 알고리즘을 활용하여 MST를 구해준다.

MST를 구한 후, 최종적으로 모든 간선 Cost - MST Cost 를 구해주면 된다.

주의 할 점은 Cost가 10^6까지 주어지므로 long long type을 사용해주어야 한다.

기본적인 MST 문제 같다.

💻 코드

//AC
//BOJ 21924 도시 건설
#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 101010
using namespace std;
typedef long long ll;
int parent[SIZE];
bool visit[SIZE];
vector<int> graph[SIZE];
struct Edge{
    int from, to, cost;
    bool operator < (const Edge& other) const{
        return cost < other.cost;
    }
};
int Find(int x){
    if(parent[x] == x)  return x;
    return parent[x] = Find(parent[x]);
}
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(y < x)   parent[y] = parent[x];
    else    parent[x] = parent[y];
}
void dfs(int x){
    visit[x] = true;
    for(int i=0; i<graph[x].size(); i++){
        if(!visit[graph[x][i]]){
            dfs(graph[x][i]);
        }
    }
}
int main(){
    int N, M;
    int from, to, cost;
    ll costSum = 0, mstSum=0;
    cin >> N >> M;
    vector<Edge> node(M);
    for(int i=0; i<M; i++){
        cin >> node[i].from >> node[i].to >> node[i].cost;
        costSum += node[i].cost;
        graph[node[i].from].push_back(node[i].to);
        graph[node[i].to].push_back(node[i].from);
    }
    
    dfs(1);
    for(int i=1; i<=N; i++){
        parent[i] = i;
        if(!visit[i]){
            printf("-1");
            return 0;
        }
    }
    sort(node.begin(), node.end());
    for(int i=0; i<M; i++){
        if(Find(node[i].from) != Find(node[i].to)){
            mstSum += node[i].cost;
            Union(Find(node[i].from), Find(node[i].to));
        }
    }
    ll ans = costSum - mstSum;
    printf("%lld", ans);
    return 0;
}