백준 16562. 친구비

문제

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

16562번: 친구비

문제풀이

 학생들을 집합으로 묶을 때 비용을 최솟값으로 저장하면서 풀이가 가능 하다. 그래서 유니온 파인드를 사용해서 풀었다.
1. 친구관계 M개를 입력 받을 때, 학생들을 하나의 집합으로 합쳐준다.(union)
2. 해당집합을 합치면서 최솟값을 저장하고, 한쪽은 0으로 만든다. (union)
3. 저장된 최솟값들을 더한다음 k와 비교하여 k보다 크면 "Oh no", 작으면 그 수를 출력한다.

소스코드(Java)

package baek;

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

/**
 * 친구비
 * https://www.acmicpc.net/problem/16562
 */
public class baek16562 {
	static int[] p, arr; //친구 관계 집합 배열과 값을 저장 할 배열

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		p = new int[N + 1];
		arr = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			p[i] = i;		//친구관계 초기화
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			union(a, b);
		}
		int answer = 0;
		for (int i = 1; i <= N; i++) {
			answer += arr[i];
		}
		if (answer > k) {
			System.out.println("Oh no");
		} else {
			System.out.println(answer);
		}
	}

	static void union(int a, int b) {
		a = find(a);
		b = find(b);

		if (a != b) {
			p[b] = a;
			arr[a] = Math.min(arr[a], arr[b]);
			arr[b] = 0;
		}
	}

	static int find(int x) {
		if (x == p[x]) {
			return x;
		}
		return p[x] = find(p[x]);
	}
}