16562. 친구비

오랜만에 문제 풀이를 작성해 본다.

16562번: 친구비

---

친구를 돈으로 사려는 불쌍한 준석이의 이야기이다. 음.. 나름 꿀알바 같기도 하고?

 

친구의 친구는 친구다라는 말이 매우 중요하다. 준석이가 학생 $i$와 친구가 되었다고 해 보자. 친구의 친구는 친구이므로 준석이는 학생 $i$번의 친구와도 친구이다. 같은 원리로 학생 $i$번의 친구의 친구와도 친구이다. 따라서 서로 친구인 그룹의 구성원 중 한 명에게만 돈을 주면 그 그룹의 모든 사람과 친구가 될 수 있다. 이때 당연히 친구비가 가장 싼 친구 한 명에게만 돈을 줘야 한다.

 

주어진 친구 관계를 그래프로 나타내고, 그래프를 탐색하여 친구 그룹을 찾을 수 있다. 각 그룹에서 가장 싼 친구비의 합을 구하자. 이 값이 $k$ 이하라면 준석이는 모든 학생과 친구가 될 수 있고, 그렇지 않다면 Oh no...

주의

나는 친구의 친구는 친구다라는 말을 잘못 이해했다. 그래프에서 인접한 한 개의 노드에만 친구 관계가 뻗어나가는 걸로 생각했다. DP로 풀어야 하나 고민하고 있었는데, 아무리 생각해도 이상해서 다시 읽어보니 내가 틀렸더라.

---

이게 골드 3? 실1~골5 정도가 적당하지 않나.