[백준] 2887번 : 행성 터널

문제

 

---

풀이

 

입력이 100,000개까지 들어올 수 있어서 행성 하나하나마다 모두 거리를 구하면 메모리 초과가 발생한다.

그렇다면 MST에 들어올 가능성이 있는 거리만 저장해야 하는데 그걸 도대체 어떻게 알까? 이 부분 때문에 힘들었다.

 

두 행성을 연결하는 비용을 살펴보자. 보통의 좌표간 거리 구하기 공식이 아니라 x, y, z 좌표의 차이의 절댓값 중 가장 작은 값을 터널 비용으로 한다고 적혀있다. 그럼 문제를 단순화 해서 x좌표만 존재한다고 하자.

 

그럼 당연히 예제 입력 1에 대한 MST는

(-1) - (10) - (11) - (14) - (19)로 20일 것이다.

 

그니까 만약에 최종적으로 x좌표의 차이의 절댓값을 MST의 간선으로 사용하게 된다면...그것은

(-1) - (10), (10) - (11), (11) - (14), (14) - (19) 중 하나라는 것이다.

결국 x, y, z좌표를 기준으로 한번씩 정렬하고 그 결과에서 인접한 행성들 간의 거리만 우선순위 큐에 넣어주면 된다.

사실 여기까지 이해하는게 좀 어렵긴 했는데 뭐...계속 들여다보면 된다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;

priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> pq; //min-heap
vector<int> parent;
vector<vector<pp>> planet; //행성 정보

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

bool unionInput(int x, int y) {
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합, 이 간선 쓸 수 없음
        return false;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
    return true;
}

int kruskalMst(int V) {
    int cnt = 0, weight = 0;

    while (cnt != (V - 1)) { //사용한 간선이 V-1개이면 break
        int dist = pq.top().first; //간선의 weight
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();
        if (unionInput(x, y)) { //x, y를 유니온할 수 있다면
            cnt++;
            weight += dist;
        }
    }
    return weight; //그래프의 가중치 합
}

int main() {
    int N, x, y, z;

    cin >> N;
    parent.assign(N, -1);
    planet.assign(3, vector<pp>(N, make_pair(0, 0)));
    for (int i = 0; i < N; i++) { //x, y, z 좌표와 기존의 인덱스 저장
        cin >> x >> y >> z;
        planet[0][i] = make_pair(x, i);
        planet[1][i] = make_pair(y, i);
        planet[2][i] = make_pair(z, i);
    }
    for (int i = 0; i < 3; i++) {
        sort(planet[i].begin(), planet[i].end()); //x, y, z에 대해 정렬
        for (int j = 0; j < planet[i].size() - 1; j++) { //x, y, z에 대해 인접한 행성끼리만 거리 구하기
            int distance = planet[i][j + 1].first - planet[i][j].first;
            pq.push(make_pair(distance, make_pair(planet[i][j + 1].second, planet[i][j].second)));
        }
    }
    cout << kruskalMst(N);
}

전체 소스코드다.

우선순위 큐에 거리를 입력하는 부분 빼고는

 

myunji.tistory.com/371

[백준] 1774번 : 우주신과의 교감

이 문제와 거의 비슷한 코드다.

 

    planet.assign(3, vector<pp>(N, make_pair(0, 0)));
    for (int i = 0; i < N; i++) { //x, y, z 좌표와 기존의 인덱스 저장
        cin >> x >> y >> z;
        planet[0][i] = make_pair(x, i);
        planet[1][i] = make_pair(y, i);
        planet[2][i] = make_pair(z, i);
    }

일단 각 행성의 x, y, z 좌표를 저장하는데 나중에 정렬할거니까 원래의 인덱스도 저장한다.

 

	0	1	2	3	4
0(=x)	11, 0	14, 1	-1, 2	10, 3	19, 4
1(=y)	-15, 0	-5, 1	-1, 2	-4, 3	-4, 4
2(=z)	-15, 0	-15, 1	-5, 2	-1, 3	19, 4

예제 입력 1의 경우 이렇게 저장된다.

 

    for (int i = 0; i < 3; i++) {
        sort(planet[i].begin(), planet[i].end()); //x, y, z에 대해 정렬
        for (int j = 0; j < planet[i].size() - 1; j++) { //x, y, z에 대해 인접한 행성끼리만 거리 구하기
            int distance = planet[i][j + 1].first - planet[i][j].first;
            pq.push(make_pair(distance, make_pair(planet[i][j + 1].second, planet[i][j].second)));
        }
    }

그리고 x, y, z에 대해 정렬을 한다.

인접한 j, j+1 행성에 대해서만 거리를 구하고 우선순위 큐에 넣는다.

 

그리고나서 그냥 kruskalMst를 호출하면 된다. 이건 1774번과 같으니 설명하지 않겠다.