백준 16562번 : 친구비

 문제

www.acmicpc.net/problem/16562

16562번: 친구비

16562 친구비

 

 구현 방법

 union-find 알고리즘을 통해 구현하였습니다.

학생 수 n 만큼의 집합을 만들고 m 만큼의 친구 관계를 통해 친구 관계를 연결해줍니다.

최소 비용을 출력해야하므로 친구 관계 연결 시 루트를 비교해서 가중치가 더 작은 노드를 루트로 올려줍니다.

모두 연결 후 연결되지 않은 친구를 구한 후 가중치를 더해 친구비를 계산해줍니다.

가지고 있는 돈 k 보다 작으면 모든 학생을 친구로 만들 수 있으므로 해당 비용 출력, 가지고 있는 돈보다 친구 비용이 더 크면 다 사귈 수 없으므로 "oh no"를 출력해줍니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B16562_친구비 {
	static int N, M, K;
	static int[] parents, weight;
	
	static void makeSet() {
		for (int i=1;i<=N;i++) {
			parents[i] = -1;
		}
	}
	
	static int findSet(int x) {
		if (parents[x]<0) return x;
		return parents[x] = findSet(parents[x]);
	}
	
	static void union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot==bRoot) return;
		
		if (weight[aRoot]<weight[bRoot]) parents[bRoot] = aRoot; // 가중치가 더 작은 것이 루트로
		else parents[aRoot] = bRoot;	
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		weight = new int[N+1];
		parents = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i=1;i<=N;i++) {
			weight[i] = Integer.parseInt(st.nextToken());
		}
		makeSet(); // 친구 집합 생성
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			union(v, w);
		}
		
		int ans = 0;
		for (int i=1;i<=N;i++) {
			if (parents[i]<0) ans+=weight[i]; // 연결되지 않은 친구 비용 계산
		}
		if (ans<=K) System.out.println(ans);
		else System.out.println("Oh no");
	}
}

 

정답!