[백준] 16562 친구비 - Java

 

 

 

문제 출저

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

16562번: 친구비

 

 

문제 풀이

 

문제

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

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

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

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

 

 

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

 

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

 

 

 

문제 풀이

 

친구 관계 : union - find를 통해 친구 관계를 구합

친구 그룹 : Map을 이용해 그룹별 친구들을 모음 

그룹별 최소 금액 : 그룹별로 반복문을 통해 가장 작은 값을 찾고 그 값을 더함

소유금 k와 비교 : 소유금과 최소 금액을 비교하여 정답 출력 

 

 

 

 

소스코드

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


/*
친구비
https://www.acmicpc.net/problem/16562

유니온 파인드를 통해 친구 그룹을 파악한다.
각각의 그룹의 최소 비용을 선택해서 더한다.
k원과 비교해서 k원이 크다면 최소 비용을 출력하고 최소 비용이 크다면 oh no를 출력한다.


4%
밤위 수정

29% 오답 
금액 long으로 변경
그룹을 지을 때 find를 사용
 */

public class Main {

    static int n;
    static int m;
    static int k;
    static long[] moneys;
    static int[] parents;
    static Map<Integer, List<Integer>> groups;


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

        moneys = new long[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n+1; i++) {
            moneys[i] = Long.parseLong(st.nextToken());
        }

        parents = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());

            union(one, two);
        }

        // 친구 그룹 짓기
        groups = new HashMap<>();
        for (int i = 1; i < n + 1; i++) {
            int index = find(i);
            if (groups.containsKey(index)) {
                groups.get(index).add(i);
            }
            else {
                List<Integer> group = new ArrayList<>();
                group.add(i);
                groups.put(index, group);
            }
        }

//        System.out.println(Arrays.toString(moneys));
//        System.out.println(Arrays.toString(parents));


        // 그룹별 적은 금액 합산
        long money = 0;
        for (int index : groups.keySet()) {
            long smallMoney = Integer.MAX_VALUE;
            for (int number : groups.get(index)) {
                smallMoney = Math.min(smallMoney, moneys[number]);
            }
            // System.out.println(index + " " + smallMoney);
            money += smallMoney;
        }

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



    }


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

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

        if (x == y) return;

        if (x < y) {
            parents[y] = x;
        } else {
            parents[x] = y;
        }
    }

}