백준 16562 - 친구비

백준 16562 - 친구비

https://www.acmicpc.net/problem/16562

★ 풀이

최소 비용으로 모든 친구들과 친구를 맺어야 한다. 전제조건은 친구의 친구는 모두 친구이다.

전제조건을 보고 집합을 만들어서 풀면 편하겠다는 생각을 했고, 유니온 파인드를 이용해서 병합해주었다.

구상은 아래와 같다.

1. 친구끼리 집합을 만들고

2. 집합 마다 가장 작은 친구 비용을 찾아서

3. 그 값을 모두 더해주면 => 모든 친구와 친구를 맺을 수 있는 최소 비용

4. 최소 비용이 k보다 작거나 같으면 최소 비용을 출력, 그 외에는 불가능 하므로 Oh no 출력

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 스킬 흡수하기 public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n,m,k; static int cost[],parent[],rank[]; static final int INF = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); cost = new int[n + 1]; parent = new int[n + 1]; rank = new int[n + 1]; for(int i = 1; i<=n; i++) { parent[i] = i; } st = new StringTokenizer(br.readLine()); for(int i = 1; i<=n; i++) { cost[i] = Integer.parseInt(st.nextToken()); } for(int i = 0; i rank[b]) { int tmp = a; a = b; b = tmp; } parent[a] = b; if(rank[a] == rank[b]) rank[b]++; } static int find(int u) { if(parent[u]== u) return u; return parent[u] = find(parent[u]); } }

from http://sweet-smell.tistory.com/152 by ccl(A) rewrite - 2021-12-09 17:01:56