MST (최소 신장 트리)

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

1197번: 최소 스패닝 트리

유니온 파인드를 사용한 크루스칼 알고리즘으로 MST를 구해보았다.

#include<bits/stdc++.h>
using namespace std;

int n,m; //정점 간선 수
int ans;
int parent[10'003];
int rnk[10'003];
vector<tuple<int,int,int>> E;

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
        rnk[i]=1;
    }
}

int find(int u){
    if(parent[u]==u) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    if(rnk[u]>rnk[v]) swap(u,v);
    parent[u]=v;
    if(rnk[u]==rnk[v]) rnk[v]++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    init();
    while(m--){
        int a,b,c; cin>>a>>b>>c;
        E.push_back({c,a,b});
    }
    sort(E.begin(),E.end());
    for(auto val : E){
        auto[g,u,v]=val;
        if(find(u)!=find(v)){
            merge(u,v);
            ans+=g;
        }
    }
    cout<<ans;
    return 0;
}

---

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

1368번: 물대기

전에 그래프 문제 중 지하철? 역을 연결하는 문제와 비슷하다.

가상의 노드를 추가시켜야 한다.

예제 케이스를 보면, 1 2 3 4 로 이어지는 가상의 정점 5를 만들고 각 간선의 가중치를 우물을 파는 비용으로 하는 것이다.

이런 발상을 떠올리기가 정말 어렵다고 생각한다.

#include<bits/stdc++.h>
using namespace std;

int parent[303];
int n,ans;
vector<tuple<int,int,int>> edge;

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        edge.push_back({x,i,n+1});
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x; cin>>x;
            if(i==j) continue;
            if(i<j) edge.push_back({x,i,j}); 
        }
    }
    sort(edge.begin(),edge.end());
    for(auto val : edge){
        auto[g,u,v]=val;
        if(find(u)==find(v)) continue;
        merge(u,v);
        ans+=g;
    }
    cout<<ans;
    return 0;
}

---

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

9372번: 상근이의 여행

모든 간선의 가중치를 1로 정의하고 크루스칼 알고리즘으로 MST를 구해준다.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int parent[1003];
vector<tuple<int,int,int>> edge;

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[u]=v; //v에 u를 붙임
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--){
        cin>>n>>m;
        int ans=0;
        edge.clear();
        init();
        while(m--){
            int u,v; cin>>u>>v;
            edge.push_back({1,u,v});
        }
        sort(edge.begin(),edge.end());
        for(auto E : edge){
            auto[g,u,v]=E;
            if(find(u)!=find(v)){
                merge(u,v);
                ans+=g;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

---

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

16398번: 행성 연결

그냥 크루스칼로 MST를 구현하면 된다.

rnk를 사용한 최적화를 하지 않아서 메모리와 시간이 많이 걸린다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans=0;
int n;
int parent[1003];
vector<tuple<int,int,int>> edge;

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return; 
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x; cin>>x;
            if(i>=j) continue;
            edge.push_back({x,i,j});
        }
    }
    sort(edge.begin(),edge.end());
    for(auto val : edge){
        auto[g,u,v]=val;
        if(find(u)==find(v)) continue;
        merge(u,v);
        ans+=g;
    }
    cout<<ans;
    return 0;
}

---

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

1647번: 도시 분할 계획

MST를 구하고, 가장 마지막에 이은 간선. 즉, 가장 비용이 비싼 간선을 ans에서 빼주면 답이 나온다.

문제를 잠깐 보고 이런 풀이를 생각했는데 올바른 풀이라 뿌듯했다.

#include<bits/stdc++.h>
using namespace std;

int n,m,ans,lastG;
vector<tuple<int,int,int>> edge;
int parent[100'003];
int rnk[100'003];

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
        rnk[i]=1;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    if(rnk[u]>rnk[v]) swap(u,v);
    parent[u]=v;
    if(rnk[u]==rnk[v]) rnk[v]++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    init();
    while(m--){
        int g,u,v; cin>>u>>v>>g;
        edge.push_back({g,u,v});
    }
    sort(edge.begin(),edge.end());
    for(auto val : edge){
        auto[g,u,v]=val;
        if(find(u)==find(v)) continue;
        merge(u,v);
        ans+=g;
        lastG=g;
    }
    ans-=lastG;
    cout<<ans;
    return 0;
}

---

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

13418번: 학교 탐방하기

풀다가 이렇게 화가 난 적은 오래간만이었다...

오르막길이 0, 내리막길이 1이므로 가중치가 0인 간선을 만났을 때 카운트를 증가시켜야 하는데, 내리막길일 때 증가시키게 해서 5번 틀렸었다.

주의하자...

#include<bits/stdc++.h>
using namespace std;

int n,m;
int parent[1003];
vector<tuple<int,int,int>> edge;

void init(){
    for(int i=0;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[v]=u;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m; m++;

    while(m--){
        int u,v,g; cin>>u>>v>>g;
        edge.push_back({g,u,v});
    }

    //최악의 경우 (오르막(=0) 우선으로 감)
    int Worst=0; init();
    sort(edge.begin(),edge.end());
    for(auto val : edge){
        auto[g,u,v]=val;
        if(find(u)==find(v)) continue;
        merge(u,v);
        if(g==0) Worst++;
    }

    //최적의 경우 (내리막(=1) 우선으로 감)
    int Best=0; init();
    sort(edge.begin(),edge.end(),greater<>());
    for(auto val : edge){
        auto[g,u,v]=val;
        if(find(u)==find(v)) continue;
        merge(u,v);
        if(g==0) Best++;
    }
    cout<<Worst*Worst - Best*Best;
    return 0;
}

 

---

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

1774번: 우주신과의 교감

n이 1000이라 n(n-1)/2 가 크지 않아 모든 간선을 vector에 넣고 MST를 돌리는 방식으로 구현했다.

n이 작아서 해결이 가능했는데 뒤에 풀 2887 행성 터널에서는 이런 방식이 불가능할 것 같다.

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define x first
#define y second

ld ans;
int n,m;

pair<int,int> node[1003];
vector<tuple<ld,int,int>> edge;
int parent[1003];

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cout<<fixed;
    cout.precision(2);

    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++){
        int x,y; cin>>x>>y;
        node[i]={x,y};
    }
    while(m--){
        int a,b; cin>>a>>b;
        merge(a,b);
    }
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            //i와 j를 잇는 간선을 edge에 넣음
            ld g = sqrt(pow(node[i].x-node[j].x,2)+pow(node[i].y-node[j].y,2));
            edge.push_back({g,i,j});
        }
    }
    sort(edge.begin(),edge.end());
    for(auto[g,a,b] : edge){
        if(find(a)==find(b)) continue;
        ans+=g;
        merge(a,b);
    }
    cout<<ans;
    return 0;
}

---

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

10423번: 전기가 부족해

이미 지어진 발전소끼리 연결하는 가상의 노드를 만들어 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;

int n,m,k,ans;
int parent[1030];
vector<tuple<int,int,int>> edge;

void init(){
    //n+1번 node는 이미 설치되어있는 발전소를 잇는 노드
    for(int i=1;i<=n+1;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(parent[u]==u) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    init();
    for(int i=1;i<=k;i++){
        int x; cin>>x;
        merge(n+1,x);
    }
    while(m--){
        int u,v,w; cin>>u>>v>>w;
        edge.push_back({w,u,v});
    }
    sort(edge.begin(),edge.end());
    for(auto [g,u,v] : edge){
        if(find(u)==find(v)) continue;
        merge(u,v);
        ans+=g;
    }
    cout<<ans;
    return 0;
}

 

---

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

2887번: 행성 터널

n이 10만이므로 최대 50억개의 간선을 살펴보는 경우가 있을 수 있기에 모든 간선을 고려하는 방법은 불가능하다. 그래서 정렬을 통해 이어질 가능성이 있는 간선만 추가해서 MST를 구성해야 한다.

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x1B/solutions/2887.cpp

해당 코드를 참고해서 코드를 작성했다.

#include<bits/stdc++.h>
using namespace std;
#define Pii pair<int,int>
#define Tiii tuple<int,int,int>
#define x first
#define y second

int n,ans,cnt;
int parent[100003];
Pii arrX[100003];
Pii arrY[100003];
Pii arrZ[100003];
vector<Tiii> edge;

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    init();

    for(int i=1;i<=n;i++){
        int x,y,z; cin>>x>>y>>z;
        arrX[i]={x,i};
        arrY[i]={y,i};
        arrZ[i]={z,i};
    }

    sort(arrX+1,arrX+n+1);
    sort(arrY+1,arrY+n+1);
    sort(arrZ+1,arrZ+n+1);

    for(int i=2;i<=n;i++){
        edge.push_back({abs(arrX[i-1].x-arrX[i].x),arrX[i-1].y,arrX[i].y});
        edge.push_back({abs(arrY[i-1].x-arrY[i].x),arrY[i-1].y,arrY[i].y});
        edge.push_back({abs(arrZ[i-1].x-arrZ[i].x),arrZ[i-1].y,arrZ[i].y});
    }

    sort(edge.begin(),edge.end());

    for(auto[g,u,v] : edge){
        if(find(u)==find(v)) continue;
        ans+=g;
        cnt++;
        merge(u,v);
        //if(cnt==n) break;
    }
    cout<<ans;
    return 0;
}