MST 이야기

어떤 그래프의 Minimum Spanning Tree란, 모든 정점을 연결하는 / 간선들의 cost합이 최소인 / 주어진 그래프의 부분그래프이다.

 

MST에는 흥미로운 성질들이 꽤나 많이 존재하며, 이를 이용한 문제들도 꽤나 많이 존재한다.

내가 문제를 많이 풀어본 것은 아니나, 지금까지 공부한 문제중에서 이를 사용하는 흥미로운 문제 두 개를 소개한다.

 

 

BOJ 8632. Byteland (from JPOI 2007)

 

각 간선에 대하여, 해당 간선을 포함하는 MST가 하나라도 존재하는지를 판별하는 문제이다.

 

다들 알다시피, 하나의 그래프에서는 여러 개의 MST가 존재할 수 있다.

Kruscal Algorithm을 생각해 보면, 간선들의 cost를 정렬하고 순서대로 각 간선들을 확인해본다.

 

여기서 다음의 성질들을 확인할 수 있다;

간선들의 cost의 multiset은 항상 동일하다.

Kruscal Algorithm을 통해 만들어진 multiset이 해당 multiset이다.

해당 multiset이 MST를 이루기 때문에,

- 어떤 cost가 자신보다 더 큰 cost를 대체할 수 있다면, Kruscal Algorithm을 제대로 안 돌린 것이다. 해당 알고리즘은 가장 작은 cost부터 차례대로 사용할 수 있을때 바로바로 사용해주기 때문이다.

- 어떤 cost가 자신보다 더 작은 cost를 대체할 수 있다면, ...대체하면 그건 '최소 cost 합'이 아니게 된다.

따라서, 간선들의 cost의 multiset은 항상 동일하다.

 

Kruscal Algorithm에서, 같은 cost의 간선 간에는 정렬 순서가 상관없다.

증명은 생략한다.

 

이 문제의 풀이는, Kruscal Algorithm을 사용하되, 간선들을 cost로 묶어서 생각한다. 각 cost의 간선들에 대해서, union을 시도하기 전에 union이 가능한지만 판별하고(여기서 union이 가능하다는 것은 해당 간선을 사용하는 mst가 존재함과 동치이다), 판별이 끝난 이후에 실제로 union한다.

 

시간복잡도는 $O(MlogM)$이다.

 

 

BOJ 24953. Reconstruction Project (from JOISC 2022)

 

쿼리로 x가 주어진다. 각 간선들의 실제 cost를 |x-w|라고 할 때, 각 x에 대하여 MST의 cost를 구하는 문제이다.

 

x가 0부터 inf까지 증가할 때, 각 간선들은 한번씩 MST에 추가되고 삭제된다(끝까지 삭제되지 않을 수도 있긴 하다).

각 간선이 언제 MST에 추가되고 삭제되는지 알 수 있다면 투포인터를 통해 문제를 해결할 수 있을 것이다.

 

어떤 간선이 MST에 추가될 때 삭제되는 간선을 해당 간선을 '대체'한다고 하자.

간선을 cost 기준으로 정렬하고, 순서대로 Spanning Tree에 추가해보자.

어떤 u-v 간선을 추가할 때 대체하는 간선은 (그리디하게 생각해보면) 현재 Spanning Tree 상의 u-v 경로에서 가장 cost가 작은 간선을 대체하는 것이 이득이다. 대체되는 시점은 해당 두 간선의 cost의 평균이다.

 

이제, 실제로 x가 증가함에 따라 변화하는 최적의 MST 상에서, 각 간선이 대체하는 간선은 위의 과정에서 자신이 대체한 간선이다.

- 자신과 자신이 대체한 간선 사이에 먼저 등장한 간선은 해당 간선을 대체하지 못하였고,

- 나보다 늦게 등장하는 간선은 해당 간선을 더 늦게 대체한다.

- 따라서, 대체하는 시점을 생각해 본다면, 실제로 x가 증가함에 따른 최적의 MST 변화 상에서도 내가 해당 간선을 대체하게 된다.

 

시간복잡도는 $O(NM+MlogM+Q)$이다.