[백준 16562] 친구비

 

유니온파인드 문제이다.

정답률이 높아서 쉬운줄 알았는데 꽤나 애먹었다.

 

아래와 같은 방법으로 풀었다.

1. 친구관계를 기록할 배열, 친구비용 배열, 친구번호와 비용을 모두 가진 클래스 배열을 만든다.

2. 친구관계가 주어지면 union 연산을 한다.

3. 클래스 배열의 루트 인덱스에 친구 비용의 최솟값을 저장한다.

4. k가 최솟값의 총합보다 같거나 크면 비용을 출력한다.

 

 

public class Main {
    
    static int a[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        a = new int[n+1];
        int cost[] = new int[n+1];
        Pair root[] = new Pair[n+1];
        for(int i=1; i<=n; i++)
            root[i] = new Pair(i, 0);
        Arrays.fill(a, -1);
        
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
            cost[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            union(v, w);
        }
        
        for(int i=1; i<=n; i++) {
            int r = find(i);
            root[r].idx = r;
            if(root[r].cost == 0) root[r].cost = cost[i];
            else root[r].cost = Math.min(root[r].cost, cost[i]);
        }
        
        int total = 0;
        for(int i=1; i<=n; i++) {
            if(root[i].cost != 0)
                total += root[i].cost;
        }
        if(k >= total)
            System.out.println(total);
        else
            System.out.println("Oh no");
    }
    
    public static int find(int n) {
        if(a[n] < 0) return n;
        a[n] = find(a[n]);
        return a[n];
    }
    
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return;
        a[x] += a[y];
        a[y] = x;
    }
    
    static class Pair {
        int idx;
        int cost;
        
        Pair(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
}