[백준][C++] 1774 우주신과의 교감

1774. 우주신과의 교감
문제 풀이

1774번: 우주신과의 교감

 

지금까지와는 다르게, 가중치가 주어지지 않고 점과 점 사이의 거리가 가중치인 문제였다.

크루스칼을 구현하는 능력이 부족한 것 같아, 크루스칼 알고리즘을 이용해서 구현해봤다.

 

알고리즘 설계

1. 노드의 번호, x, y 좌표를 저장해준다.
2. 저장한 노드들 사이에 모든 간선을 구한다. 간선 = { A노드, B노드, A와 B 사이의 거리 (가중치) }

1. 구한 간선들을 가중치를 기준으로 오름차순 정렬해준다.
2. 사이클이 생기지 않게 간선을 선택하여 MST를 만들고 비용을 구한다.
3. union-find + memoization

 

코드

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

// 위치와 아이디를 가진 구조체
struct Node
{
    pair<int, int> pos;
    int id;
};

// 간선 구조체
struct Edge
{
    int a, b;
    double dist;

    bool operator < (const Edge& e) const
    {
        return dist < e.dist;
    }
};

int parents[1001];
vector<Node> nodes;
vector<Edge> edges;

// union-find
int find(int v)
{
    vector<int> memo;

    while (parents[v] != v)
    {
        v = parents[v];
        memo.push_back(v);
    }

    for (int i : memo)
        parents[i] = v;

    return v;
}
bool uni(int a, int b)
{
    int fa = find(a), fb = find(b);

    if (fa != fb)
    {
        parents[fa] = fb;
        return true;
    }

    return false;
}

// 점과 점 사이의 거리 구하기
double GetDist(pair<int, int> p1, pair<int, int> p2)
{
    return sqrt((ulli)pow(p1.first - p2.first, 2) + (ulli)pow(p1.second - p2.second, 2));
}

int main()
{
    int vCnt, lCnt, x, y;
    double result = 0;
    cin >> vCnt >> lCnt;

    // 각 노드의 위치를 입력 받는다
    for (int i = 1; i <= vCnt; i++)
    {
        cin >> x >> y;

        parents[i] = i;
        nodes.push_back(Node{ {x, y}, i });
    }

    // 이미 정해진 경로를 입력 받는다
    for (int i = 0; i < lCnt; i++)
    {
        cin >> x >> y;
        uni(x, y);
    }

    // 만들 수 있는 모든 간선을 만들어
    // Edge 벡터에 넣는다
    for (int i = 0; i < vCnt; i++)
    {
        for (int j = 0; j < vCnt; j++)
        {
            if (i == j) continue;

            double dist = GetDist(nodes[i].pos, nodes[j].pos);
            edges.push_back({ nodes[i].id, nodes[j].id, dist });
        }
    }

    // 오름차순 정렬
    // 크루스칼
    sort(edges.begin(), edges.end());

    // 사이클이 생기지 않게 가중치를 더함
    for (int i = 0; i < edges.size(); i++)
    {
        if (uni(edges[i].a, edges[i].b))
        {
            result += edges[i].dist;
        }
    }

    // 소수점 둘째 자리까지 출력
    cout << fixed;
    cout.precision(2);
    cout << result;
}

오랜만에 MST 문제를 풀고, 더해 어렵지 않은 수학적 개념까지 들어간 문제를 풀어서 기분이 좋았다!!