백준 1774 - 우주신과의 교감(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

 

문제 조건

출력 예시

간단한 MST 문제였습니다. 본격적인 쿠르스칼 알고리즘을 실행하기 전에 연결되어 있는 지점들을 연결해주고 시작하는게 포인트였습니다.

 

    for (int i = 0; i < num_link; i++) {
        int x, y;
        cin >> x >> y;
        Union(x, y);
    }

연결되어 있는 지점을 입력 받은 뒤에 Union함수를 통해서 연결해줬습니다. 

 

    for (int i = 0; i < num; i++) {
        for (int j = i + 1; j < num; j++) {
            double x_distance = abs(place[i].first - place[j].first);
            double y_distance = abs(place[i].second - place[j].second);
            double distance = sqrt(x_distance * x_distance + y_distance * y_distance);
            planet.push_back({ i + 1, j + 1, distance });
        }
    }

1번 지점부터 N번까지 하나하나 거리를 계산해서 입력해줬습니다. abs와 sqrt를 이용해 쉽게 계산했습니다.

 

Union + Find 를 통해서 한 지점이 어디까지 연결되어있는지를 찾은뒤에 연결해줬습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

vector<pair<double, double>> place;
typedef struct li {
    int start;
    int finish;
    double cost;
}li;
vector<li> planet;
int num, num_link;
int connect[1001];

bool cmp(li a, li b) {
    if (a.cost < b.cost) return true;
    return false;
}

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}

void solve() {
    double cost_mini = 0;
    for (int i = 0; i < num; i++) {
        for (int j = i + 1; j < num; j++) {
            double x_distance = abs(place[i].first - place[j].first);
            double y_distance = abs(place[i].second - place[j].second);
            double distance = sqrt(x_distance * x_distance + y_distance * y_distance);
            planet.push_back({ i + 1, j + 1, distance });
        }
    }
    sort(planet.begin(), planet.end(), cmp);
    for (int i = 0; i < planet.size(); i++) {
        int x = Find(planet[i].start);
        int y = Find(planet[i].finish);
        if (x != y) {
            Union(x, y);
            cost_mini += planet[i].cost;
        }
    }
    printf("%.2f", cost_mini);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num >> num_link;
    for(int i = 0; i < num; i++){
        double x, y;
        cin >> x >> y;
        place.push_back(make_pair(x, y));
    }
    for (int i = 0; i < 1001; i++) connect[i] = i;
    for (int i = 0; i < num_link; i++) {
        int x, y;
        cin >> x >> y;
        Union(x, y);
    }
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!