최소신장트리. [2887]

[1. 문제 설명]

3차원 좌표 상 점들을 직접/간접적으로 모두 연결 하고자 할 때, 필요한 최소비용을 구한다.

점 간의 연결을 위한 비용은 아래와 같이 구한다.

A: (x1, y1, z1) / B: (x2, y2, z2)

=> min(|x1-x2|, |y1-y2|, |z1-z2|)

[2. 풀이 접근]

정점의 최대개수는 100,000 으로 모든 edge 를 구하기 위한 메모리는 아래와 같다.

=> 100000²

그래서 일반적인 풀이로는 메모리 초과가 발생한다.

이 문제에서 정점 간 연결을 위한 비용은 일반적인 계산법과 다르다는 것을 이용하도록 한다.

보통 3차원 좌표 간 거리는 sqrt(dx²+dy²+dz²) 로 구한다.

그러나 여기서는 각 축에 위치한 좌표 간 거리의 최소값이 된다.

아래와 같은 수직선에서 모든 점을 최소비용으로 연결 한다고 할 때는 아래와 같이 만들고,

아래와 같이 바로 옆에 인접한 점으로 이동하지 않고 우회해서 가지 않는다.

따라서 두개의 3차원 좌표가 있을 때

하나의 축으로만 바라보고 최소 비용으로 연결하려 한다면 그림1 처럼 연결하면 될 것이다.

즉, 모든 3차원 좌표들을 하나의 축에서 가장 가깝게 인접한 것 들 끼리 묶어서 생각하는 것이다.

이렇게 하면 하나의 축에서 필요한 edge 를 O(N) 개로 줄일 수 있다.

이것을 각 축에 대해서 진행하여 모든 edge 를 구한뒤 정렬 후

최소신장트리를 만들어 보면 된다.

edge 배열을 정렬하면,

임의의 점 A 에서 B 로 가는 edge 의 비용 항상 올바르게 조정된다.

ex) ({v1, v2, cost} => {0, 1, 3}, {0, 1, 2}, {0, 1, 1}) -> ({0, 1, 1}, {0, 1, 2}, {0, 1, 3})

또한, 어떤 edge 가 mst 에 포함되면, 뒤이어 오는 같은 edge 들은 (코스트만 다른)

mst 생성에 포함되지 않게 된다,

== 실수한 점 ==

각 좌표를 정렬 후, 정점의 번호가 바뀌는 점을 놓치고 있었던 점

ex) 기존 좌표 배열이 [A][B][C][D] 였고, 정렬 후, [B][D][A][C] 이면

index:0 이 정점 A 를 가리키는 것이 아니라 정점 B 를 가리키는 것인데,

이것을 놓치고 있었음

기존 정점 번호 역시 같이 저장하도록 함.

[3. 코드]

test_kernelv2