백준 16562 (친구비) - java

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

16562번: 친구비

문제 

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

 

유형 : MST

 

접근

• 모든 친구관계가 형성되기 위해서는 즉 그래프 상에서 MST를 만드는 것이다.
• MST를 만들지 못하거나 만들었을 때 비용이 K원을 넘어간 경우에 "Oh no"를 출력해주면 된다.

MST

• 크루스칼 알고리즘을 사용했다. -> union find 구현 O(ElogE)

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;
    static int k = 0;
    static int[] cost;

    static int[] root;

    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());

        cost = new int[n+1];
        root = new int[n+1];
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        st = new StringTokenizer(br.readLine()," ");
        for(int i=1;i<=n;i++){
            cost[i] = Integer.parseInt(st.nextToken());
            root[i] = i;
            pq.add(new Node(0,i,cost[i]));
        }



        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            pq.add(new Node(x,y,0));
        }

        int result = 0;
        int num = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(find(cur.v1) != find(cur.v2)){
                union(cur.v1,cur.v2);
                result += cur.c;
                num += 1;
            }

            if(num == n)
                break;
        }

        if(num == n && result <= k){
            System.out.println(result);
        }
        else{
            System.out.println("Oh no");
        }

        br.close();
    }

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

        return root[x] = find(root[x]);
    }

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

        if(x < y)
            root[y] = x;

        else
            root[x] = y;

    }
}
class Node{
    int v1;
    int v2;
    int c;

    Node(int v1,int v2,int c){
        this.v1 = v1;
        this.v2 = v2;
        this.c = c;
    }
}