[Algorithm]Baekjoon 2887 :: 행성 터널

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 
 
using namespace std;
 
struct Node
{
    int distance;
    int node1;
    int node2;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.distance < b.distance;
}
 
int n;
vector<Node> nodes;
vector<pair<int, int>> xInfo, yInfo, zInfo;
 
int parents[100001] = { 0 };
 
int findParent(int node)
{
    if (node == parents[node]) return node;
    return parents[node] = findParent(parents[node]);
}
 
void unionParents(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
 
    if (a < b) parents[b] = a;
    else parents[a] = b;
}
 
bool isSameParents(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
 
    if (a == b) return true;
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        parents[i] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
 
        xInfo.push_back({ x,i });
        yInfo.push_back({ y,i });
        zInfo.push_back({ z,i });
    }
 
    sort(xInfo.begin(), xInfo.end());
    sort(yInfo.begin(), yInfo.end());
    sort(zInfo.begin(), zInfo.end());
    
    for (int i = 0; i < n - 1; ++i)
    {
        nodes.push_back({ xInfo[i + 1].first - xInfo[i].first, xInfo[i + 1].second, xInfo[i].second });
        nodes.push_back({ yInfo[i + 1].first - yInfo[i].first, yInfo[i + 1].second, yInfo[i].second });
        nodes.push_back({ zInfo[i + 1].first - zInfo[i].first, zInfo[i + 1].second, zInfo[i].second });
    }
    
    sort(nodes.begin(), nodes.end(), cmp);
 
    long long answer = 0;
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        if (isSameParents(nodes[i].node1, nodes[i].node2) == false)
        {
            unionParents(nodes[i].node1, nodes[i].node2);
            answer += (long long)nodes[i].distance;
        }
    }
 
    cout << answer;
}

 

문제를 읽으면 일단 MST를 만드는 문제인것은 알 수 있다.

다만, MST를 만드는 데 필요한 간선정보를 어떻게 구할것인가? 가 포인트인 문제.

x,y,z값이 주어지고 특정 노드와 비교했을 때 각 축의값의 차이의 절대값이 가장 작은걸 터널비용으로 한다고 했다.

그래서 그냥 단순하게 생각했을 때는 모든걸 다 비교해야할 것 같이 느껴진다.

물론 실제로 그렇게하면 당연히 시간제한에 걸린다. n이 최대 10만이니까

 

그래서 아예 각 축의 값을 기준으로 정렬한 컨테이너를 만든다.

축이 3개(x,y,z)니까 컨테이너(벡터)도 3개 만든다. 

예를들어 xInfo에는 x값이 오름차순정렬되어있고, 해당 x값에 해당하는 노드번호가 들어있다.

 

사실 나는 pair를 원래 잘 안썼다. 좀 더 직관적으로 보기위해 항상 구조체를 선언해서 적절한 변수명을 사용했었는데, 이런 경우에는 pair쓰면 cmp함수를 따로 작성안해줘도 되서 한번 이용해봤다.

 

쨌든, 이후 nodes에다가 각 축마다의 다음노드와의 거리값을 넣어준다.

예를들어 xInfo에는 x값이 오름차순 정렬되어있기 때문에, xInfo[1].first(위치) - xInfo[0].first 를 해주는 과정을 n-1번만큼 하게되면 x값으로 만들 수 있는 최소거리값들을 전부 구할 수 있게된다.

이런식으로 각 축마다 이 거리값들을 구해서 nodes에 넣어준다음 마찬가지로 해당 거리값을 기준으로 정렬 후에 크루스칼로직을 진행해주면 MST를 만들 수 있게된다.