[BOJ]16562:친구비

그래프의 union-find알고리즘을 사용하여 해결하였다.

1. 친구의 수만큼 배열을 만들어  make(int N)함수로 N+1개만큼 parent정보를 담는 배열을 생성한다(처음에 부모는 나 자신)

2. 주어진 친구의 정보에 따라 union을 한다. 이때, 친구비용이 더 작은 친구를 그룹 대표(즉 부모)로 잡는다

3. 마지막에 모든 노드에 대해 findSet함수를 이용하여 최종 부모를 배열에 저장한다

4. HashSet을 사용하여 집합의 갯수만큼 친구를 사귈수 있는 비용을 모두 구하고 내가 가진 돈이랑 비교하면 끝!

 

github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/%EA%B7%B8%EB%9E%98%ED%94%84/p16562.java

SuyeonChoi/Algorithms

 

union find를 안다면 매우 쉬운 수준이다