[백준 16562] 친구비 with JAVA

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”(따옴표 제거)를 출력한다.

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

public class p16562 {
    static int N, M;
    static int[] parent;
    static int[] min;
    static int[] cost;
    static int ans = 0;
    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());
        cost = new int[N];
        parent = new int[N];
        min = new int[N];
        init();
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++){
            cost[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(min, Integer.MAX_VALUE);

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken()) - 1;
            int v2 = Integer.parseInt(st.nextToken()) - 1;
            if (v1 > v2) union(v1, v2);
            else union(v2, v1);
        }
        for (int i = 0; i < N; i++){
            int root = find(i);
            min[root] = Math.min(min[root], cost[i]);
        }
        sol();
        if (ans > K) System.out.println("Oh no");
        else System.out.println(ans);
    }
    public static int find(int x){
        if (x == parent[x]) return x;
        else return parent[x] = find(parent[x]);
    }
    public static void union(int x, int y){
        x = find(x);
        y = find(y);
        if (x != y) parent[y] = x;
    }
    public static void init(){
        for (int i = 0; i < N; i++){
            parent[i] = i;
        }
    }
    public static void sol(){
        for (int i = 0; i < N; i++){
            if (min[i] != Integer.MAX_VALUE) ans += min[i];
        }
    }
}

1. 어려웠던 점:

- find(x)로 접근하지 않고, parent[x]로 접근하게 되면, find 함수의 로직이 작동하지 않아 같은 집합이지만 다른 루트를 가리킬 수 있는 점을 착각해 몇 번 틀렸다.

 

2. 알게된 점:

- 유니온 파인드 복습 (union 함수 구현 중, 다소 헷갈려서 다른 날 또 다시 풀어봐야겠다, 위에 서술한 find로 접근하는 것도 잊지말자)

 

3. 알고리즘 풀이:

- 유니온 파인드로 각 분리 집합을 만든다.

min[] 배열을 만들어, 각 집합의 최솟값만을 저장한다.

이 때, min[x]의 x는 루트 노드여야한다. 그래야만, 각 원소가 같은 집합인지 알 수 있다.

마지막으로 min[x]의 초기화값 Integer.MAX_VALUE를 제외한 모든 값을 더하고

K보다 크면 Oh no 작으면 더한 값을 출력한다.