BOJ-16562 친구비

1. 문제

문제 링크 : https://www.acmicpc.net/problem/16562

알고리즘 분류 : 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합

2. 고민

이번 문제는 “친구의 친구는 친구다” 에서 union-find를 사용하면 될 것이라는 아이디어를 얻었습니다.

추가로, 한정된 돈을 가지고 친구를 얻어야 하므로 친구비를 오름차순으로 정렬해서 Greedy 방식으로

적은 금액의 친구비부터 하나씩 선택하는 방법을 생각했습니다.

3. 설계

[1] 입력 (친구관계 입력 시 union 작업)

[2] 친구비 오름차순 정렬

[3] 적은 친구비부터 하나씩 선택하면서 비용 구하기

[4] 출력

4. 코드

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

    public class Main {

        static int student, relationship, havingMoney, cost;    // 학생 수, 관계 수, 가지고 있는 돈, 비용
        static int[][] friendCosts;                             // 친구비
        static int[] parent;                                    // union-find parent
        static boolean[] isFriend;                              // 현재 친구 관계

        // 최상위 부모를 찾는 메서드
        static int find(int x) {
            if(x == parent[x])  return x;

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

        // 두 집합을 합치는 메서드
        static void union(int a, int b) {
            a = find(a);
            b = find(b);

            if(a == b)  return;

            int minValue = Math.min(a, b);
            parent[a] = minValue;
            parent[b] = minValue;
        }

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());

            // Input 학생 수, 관계 수, 가지고 있는 돈
            student = Integer.parseInt(st.nextToken());
            relationship = Integer.parseInt(st.nextToken());
            havingMoney = Integer.parseInt(st.nextToken());

            // Initialize
            parent = new int[student+1];
            friendCosts = new int[student][2];
            isFriend = new boolean[student+1];

            // Input 친구비, Initialize union-find parent
            st = new StringTokenizer(br.readLine());
            for(int idx=1; idx<=student; idx++) {
                parent[idx] = idx;
                friendCosts[idx-1][0] = idx;
                friendCosts[idx-1][1] = Integer.parseInt(st.nextToken());
            }

            // Input 친구 관계 -> union 작업
            for(int idx=0; idx<relationship; idx++) {
                st = new StringTokenizer(br.readLine());
                int personA = Integer.parseInt(st.nextToken());
                int personB = Integer.parseInt(st.nextToken());

                union(personA, personB);
            }

            // 친구비를 오름차순으로 정렬
            Arrays.sort(friendCosts, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });

            // 적은 친구비부터 하나씩 선택하면서 친구인지 확인 후 비용에 추가
            for(int idx=1; idx<=student; idx++) {
                int person = find(friendCosts[idx-1][0]);

                if(isFriend[person]) continue;

                isFriend[person] = true;
                cost += friendCosts[idx-1][1];

                if(cost > havingMoney)  break;
            }
            
            // 모든 친구를 택하는 비용이
            // 가지고 있는 돈보다 많은 경우 Oh no 출력
            // 가지고 있는 돈으로 충분한 경우 비용 출력
            System.out.println(cost <= havingMoney ? cost : "Oh no");
        }
    }

            
              📕 개인 기록용 블로그입니다.
              😊 오타나 잘못된 정보가 있을 경우 댓글이나 메일로 말씀해주시면 바로 수정하겠습니다! 😊