[백준] 16562번 친구비 문제 풀이

문제  풀이고려해야할 점더보기친구의 친구의 친구도 친구로 칠 수 있다. 즉 어떤 친구 집단 트리 A가 있을 때 그 중 한 명만 친해도 그 집단 전체와 친구가 되었다고 할 수 있다. 이를 계산하기 위해 서로 연결되어 있는 친구 집단을 구해야 한다. 이 결과를 바탕으로 친구비를 최소로 하는 경우의 수를 찾아야 한다. 중복되는 친구 관계, 혹은 자기 자신과 친구인 경우를 확인해야 한다. 모두 친구를 만들 수 없는 경우 "oh no"를 출력해야 한다.  알고리즘 분류(백준 기준) 더보기자료구조그래프 이론 그래프 탐색분리 집합유니온 파인드  풀이 아이디어 더보기집합 관계를 효율적으로 판별하기 위해 유니온 파인드를 사용하였다. 두 집합을 합칠 때는 친구비의 값이 더 싼 쪽이 부모가 되도록 결합하였다. 각 집합의 최..
알고리즘/코딩테스트 2024. 11. 5. 16:28
1