[백준(BOJ)] 1922번 : 네트워크 연결 - C++[CPP]

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

---

 

⊙ 문제 접근 과정

 

솔직히 고백할게요.

 

 

백준 1197번 문제(https://tooo1.tistory.com/199)와 코드 똑같아요. ㅋ

개념이나 풀이 방식을 원한다면 위 링크로!!!

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

#define MAX 10001
using namespace std;

int M,N;
int parent[MAX];
int result=0;
vector<tuple<int,int,int>> v;

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

void connection(int x,int y) {
    x=find(x);
    y=find(y);
    if(x!=y) {
        parent[x]=y;
    }
}

bool same(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y) return true;
    else return false;
}

int main() {
    cin >> M >> N;

    for(int i=1;i<=M;i++)
        parent[i]=i;

    for(int i=0;i<N;i++) {
        int A,B,C;
        cin >> A >> B >> C;
        v.push_back({C,A,B});
    }

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

    for(int i=0;i<N;i++) {
        if(!same(get<1>(v[i]), get<2>(v[i]))) {
            connection(get<1>(v[i]), get<2>(v[i]));
            result +=get<0>(v[i]);
        }
    }

    cout << result;
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!