백준 - 친구비 16562

---

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

16562번: 친구비

---

[문제 접근]

• union-find 알고리즘 사용
• union 함수에서 부모 설정할 때 cost가 더 낮은 친구로 설정
• 1 ~ N 까지 find 함수로 부모를 찾아 준 후 cost를 더해 주고, 방문 처리를 통해 이미 더해준 집합은 건너뜀

---

[Java]

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


public class Main
{
    static int parent[];
    static int cost[];
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        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());

        parent = new int[n+1];
        cost = 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<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            union(a,b);
        }

        int sum = 0;
        visited = new boolean[n+1];
        for(int i=1; i<=n; i++){
            int p = find(i);

            if(visited[p])
                continue;

            sum += cost[p];
            visited[p] = true;
        }

        if(k >= sum){
            System.out.println(sum);
        }else
            System.out.println("Oh no");


    }

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

        if(x == y) return;

        if(cost[x] >= cost[y])
            parent[x] = y;
        else
            parent[y] = x;
    }

    public static int find(int a){
        if(parent[a] == a) return a;

        return parent[a] = find(parent[a]);
    }



}