[Java] BOJ16562, 백준 - 친구비

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

16562번: 친구비

 

이것 또한 유니온파인드 응용문제이나, 기초가 탄탄하다면 쉽게 풀 수 있는 문제이다.
int[] parent 배열로 그룹번호를 관리해주고
int[] min 배열로 해당 그룹의 최소 친구비를 관리해주면 된다.

import java.io.*;
import java.util.*;

public class Main {

	private static int[] parent;
	private static int[] min; // 해당 그룹의 최소 친구비

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = parse(st.nextToken()); // 학생 수
		int m = parse(st.nextToken()); // 친구관계 수
		int k = parse(st.nextToken()); // 가진 돈
		min = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++)
			min[i] = parse(st.nextToken());

		makeSet(n);
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = parse(st.nextToken());
			int b = parse(st.nextToken());

			union(a, b);
		}

		// 친구비 계산
		int fee = 0;
		boolean[] check = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			int p = find(parent[i]);
			if (check[p])
				continue;
			// 방문한 적 없는 그룹만..
			check[p] = true;
			fee += min[p];
		}
		System.out.println(((k >= fee) ? fee : "Oh no"));
	}

	private static void makeSet(int n) {
		parent = new int[n + 1];
		for (int i = 1; i <= n; i++)
			parent[i] = i;
	}

	private static int find(int a) {
		if (a == parent[a])
			return a;
		else
			return parent[a] = find(parent[a]);
	}

	private static void union(int a, int b) {
		int ra = find(a);
		int rb = find(b);
		if (ra != rb) {
			// 해당 그룹의 최소 친구비를 갱신
			min[ra] = Math.min(min[ra], min[rb]);
			parent[rb] = ra;
		}
	}

	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}