백준 16562

 

16562번: 친구비

 

  제목부터 슬픈 문제. 서로 연결되어 있는 것들을 처리해야 해서 처음엔 Connected Component를 구해서 어찌어찌 처리해야 하나 했지만 친구비를 아끼기 위해 친구 집합의 최소 친구비를 구해야 된다. 트리를 이용하면 루트에 최소 친구비를 업데이트 할 수 있고 두 트리를 합칠 땐 유니온 파인드를 이용하면 된다.

 

  유니온 파인드의 merge를 구현할 때 왼쪽을 우리와 이미 친구인 집합 오른쪽을 새로 친구가 되는 집합이라 하고 한쪽으로만 붙여 나가며 루트를 업데이트 하면 구현이 간단하다.

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%2016562.cpp