최소신장트리. [1774]

[1. 문제 설명]

이미 연결된 간선이 존재하고,

아직 연결되지 않은 정점을 연결해야 할 때, 필요한 최소길이를 구한다.

정점은 2차원 평면 좌표형태로 주어진다.

[2. 풀이 접근]

먼저 피타고라스 정리를 이용하여 모든 edge 의 길이를 구하도록 한다.

정점의 개수가 N 이므로,

전체 edge 의 개수는 N(N-1)/2 이다.

문제에서 주어진 정점의 최대 개수는 1000 이므로,

edge 를 위한 메모리는 충분하다.

여기서 주의할 점은

이미 연결 된 edge 에 대한 처리이다.

이 문제의 답을 구하기 위해서는 최소신장트리를 만들고,

이미 연결된 edge 의 길이를 빼서 만들 수 있을 것 같지만,

이미 연결된 edge 를 포함해서 만들어야 하는 부분이 까다롭다.

예를들어, 아래 그림에서 실선은 문제에서 제시된 이미 연결된 edge이고

점선이 앞으로 연결해야 할 edge일 때,

이미 연결된 edge 들이 이미 cycle 을 이루기 때문에,

최소신장트리를 만들 때 cycle 을 형성하는 edge 의 길이가 포함되지 않기 때문이다.

그래서 이미 연결된 간선의 길이를 0으로 설정한다.

그러면 전체 그래프의 최소신장트리를 구하는 것 만으로

문제에 대한 답을 구할 수 있다.

edge 길이를 0으로 하면

크루스칼 알고리즘 특성 상,

mst 에 제일 먼저 포함시킬 것이며, (cycle 을 이루지 않는 한)

문제에서 제시 된 답에는 영향을 주지 않기 때문이다.

또한, 구해야 할 부분은 아직 연결되지 않은 모든 정점들을

최소한의 비용으로 연결하는 것이 목표이지,

이미 연결된 edge 를 포함하여

모든 정점을 반드시 mst 로 연결해야 한다는 것이 목표가 아니기 때문이다.

=> 이미 연결된 것은 어쩔 수 없고,

=> 주어진 간선을 일부를 반드시 포함해서 모든 정점을 최소한의 비용으로 연결 한다.

=> 반드시 포함시키기 위해, edge 의 cost 를 의도적으로 낮춰버린다.

=> 이 과정에서 cycle 을 형성하는 edge 는 포함되지 않으나,

=> 문제에서 이미 연결된 edge 로 제시되었으므로, mst 형성 후 나중에 포함시켜도 된다.

=> 물론 이때는 mst 가 아니게 되겠지만,

[3. 코드]

test_kernelv2