[BOJ][백준][JAVA] 16562 - 친구비

[문제 풀기]

16562번: 친구비

📒 문제

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

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

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

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

📒 해결방법

parent배열을 초기화하고 union-find를 통해 집합 중 최솟값을 가지는 그룹을 찾는 문제였다.

📒 소스코드

package BOJ.Graph;

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

public class boj16562_친구비 {
    static int n, m, k;
    static int[] parent;
    static int[] cost;
    static boolean[] visit;

    public static void main(String[] args) throws Exception {
        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());

        // graph = new int[n + 1][n + 1];
        cost = new int[n + 1];
        parent = new int[n + 1];
        visit = new boolean[n + 1];
        for (int i = 1; i < n + 1; i++) {
            parent[i] = i;
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i < n + 1; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            union(v1, v2);
        }
        int min = 0;
        for (int i = 1; i < n + 1; i++) {
            int cur = cost[i];
            if (visit[i] == true)
                continue;
            for (int j = 1; j < n + 1; j++) {
                if (find(i) == find(j)) {
                    cur = Math.min(cur, cost[j]);
                    visit[j] = true;
                }
            }
            min += cur;
            visit[i] = true;
        }

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

    // 들어온 value 값의 원소가 포함된 트리의 루트노드를 찾는다.
    static int find(int value) {
        // value의 루트노드가 value 일경우 즉 연결된 노드가 없다.
        if (value == parent[value])
            return value;
        return parent[value] = find(parent[value]);
    }

    // 합치기 : a와 b가 속ㅎ한 그래프를 하나로 합친다 
    // union(합집합) 두개의 루트노드를 찾고 원속값이 더 작은 루트노드를 루트노드로
    // 선택.
    static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot)
            return false;
        parent[aRoot] = bRoot;

        return true;
    }
}

 

📒 리뷰

내 제출

 

---

보자마자 유니온 파인드라는 걸 떠올리기 쉽지 않았던 문제다.. 하나하나 k에서 빼가며 확인하다가 이 방식이 아니란 걸 깨닫고 유니온 파인드로 집합 찾고 해결했다.. 어려워..