8주차(최소신장트리) - [C++]백준1774 우주신과의 교감

10 May 2022 in Study on Algorithm

백준1774 우주신과의 교감 링크

문제

예제 입력

---

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

int arr[1001];
vector<pair<int, int>> star;
vector<pair<double, pair<int, int>>> vec;

// 원소가 속한 집합 찾기  
int find(int x) {
    if (arr[x] != x) arr[x] = find(arr[x]);
    return arr[x];
}

// 두 원소 집합 합치기  
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a < b) arr[b] = a;
    else arr[a] = b;
}

int main() {
    int n , m;
    cin >> n >> m;
    // 1~N까지 사용
    for (int i = 1; i <= n; i++) arr[i] = i;

    // 정점 좌표
    int a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        star.push_back({ a, b });
    }

    // 연결된 간선 갯수
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        vec.push_back({ 0,{ a, b} });
    }

    // 간선 만들기
    for (int i = 0; i < n-1; i++) { // 벡터로 접근해서 0부터 시작해야함 마지막 정점은 이미 간선 다 있음
        for (int j = i + 1; j < n; j++) {
            double e = sqrt(pow(star[i].first - star[j].first, 2) + pow(star[i].second - star[j].second, 2));
            vec.push_back({ e, {i+1,j+1} }); 
        }
    }
    sort(vec.begin(), vec.end());

    // 크루스칼 알고리즘
    double cost = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (find(vec[i].second.first) != find(vec[i].second.second)) {
            Union(vec[i].second.first, vec[i].second.second);
            cost += vec[i].first;
        }
    }
    cout << fixed << setprecision(2) << cost;
}

설명

이 문제는 앞에서 푼 별자리 만들기와 비슷하지만 이미 연결된 간선이 있다는 것이 다른 점입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 iomanip를 사용하여 구현했습니다. 우주신들의 위치 정보를 입력 받아 MST로 최소 비용을 구해야하는데 이미 연결된 간선은 비용을 0으로 해서 제일 먼저 수행되게 만들었습니다. 그다음에 간선이 주어지지 않아서 두 위치 상에 거리를 구하는 공식 sqrt(pow(x1-x2)+pow(y1-y2))로 구하여 직접 만들어 줬습니다. 그 상태에서 크루스칼 알고리즘을 사용하기 위해서 간선을 오름차순으로 정렬하고 최소신장트리를 구하였습니다. 그리고 최소 비용을 출력할때 소수점 둘째자리 까지 허용하기 때문에 cout출력문에 설정을 2자리까지 고정시켜 출력합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<iomanip>
-fixed : 실수를 고정된 부동소수점 형식으로
-setprecision(n) : 실수의 정밀도 설정

<cmath>
-pow(val, n) : val의 n제곱
-sqrt(val) : 루트

---

결과