백준 4386 - 별자리 만들기

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

4386번: 별자리 만들기

간단한 MST문제였습니다.

 

문제 조건

출력 예시

 

문제 접근 방법

1. 백터를 통해서 좌표를 입력 받는다.

2. 1번 좌표에서 갈수 있는 다른 별들의 거리를 저장한다.

   ex) 1번에서는 2,3,4,5...등 갈수 있습니다. 따라서 구조체 백터에 시작점, 도착점, 거리를 저장한다.

        2번의 경우에는 3,4,5,6...등을 갈 수 있습니다. 1번과 똑같이 저장한다.

3. cost의 값에따라 오름차순으로 정렬한다.

4. Union + Find를 통해서 트리의 최소 비용을 구한다.

 

 

문제 접근 방법 - 2번

abs를 통해서 절대값을 저장한뒤에 제곱의 합을 sqrt를 해서 거리를 구했습니다. 그 뒤에 백터에 저장했습니다.

 

 

문제 접근 방식 - 4번 

 

cost의 값으로 오름차순 정렬을 했습니다. 그 뒤에 가장 작은 비용부터 확인합니다. 

Find() 함수를 통해서 시작점을 통해 어디까지 이어져있는지를 확인합니다. 도착점도 똑같이 확인합니다.

만약에 시작점과 도착점이 향하는 곳이 같다면 이미 이어져있는 곳이기에 확인할 필요가 없습니다. 따라서 다를 경우에만 cost를 더해준 뒤에 이어줬습니다.

 

 

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

 

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

int num;
vector<pair<double, double>> star;
typedef struct st {
    int start;
    int finish;
    double cost;
}st;
vector<st> line;
int connect[101];

void get_distance() {
    for (int i = 0; i < star.size(); i++) {
        for (int j = i + 1; j < star.size(); j++) {
            double x = abs(star[i].first - star[j].first);
            double y = abs(star[i].second - star[j].second);
            double distance = sqrt(x * x + y * y);
            line.push_back({ i + 1,j + 1,distance });
        }
    }
}

bool cmp(st a, st 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 mini = 0;
    get_distance();
    sort(line.begin(), line.end(), cmp);
    for (int i = 1; i <= 100; i++) {
        connect[i] = i;
    }
    for (int i = 0; i < line.size(); i++) {
        int x = Find(line[i].start);
        int y = Find(line[i].finish);
        if (x != y) {
            Union(x, y);
            mini += line[i].cost;
        }
    }
    printf("%0.2lf", mini);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num;
    for (int i = 0; i < num; i++) {
        double x, y;
        cin >> x >> y;
        star.push_back(make_pair(x, y));
    }
    solve();
    return 0;
}

 

 

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