백준 14574 (헤븐스 키친) - java

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

 

문제

 

남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 한 명이 천국으로 떠난다.

만일 한 명의 요리사가 남는다면 해당 요리사는 지옥으로 보내진다.

이 프로그램에 출연하는 N명의 요리사는 각각 요리 실력 Pi와 인기도 Ci를 갖고 있다.

이 프로그램의 시청률은 그 날 요리 대결을 펼치는 두 요리사의 요리 실력과 인기도에 의해 결정된다.

만일 요리사 A와 요리사 B가 대결을 펼친다면, 그 날의 시청률은 floor(CA+CB|PA−PB|)로 결정된다. 어떤 두 요리사의 요리 실력이 같은 경우는 없다.

(floor(x)는 x보다 작거나 같은 가장 큰 정수)

대결의 승패는 요리 실력이나 인기도와는 관계없이 결정될 수 있다.

남규는 이 프로그램을 시청하던 중, 요리사들의 대결 순서와 승패에 따라 프로그램의 시청률이 크게 달라질 수도 있다는 사실을 발견했다.

남규는 총 N-1번의 경기 동안, 경기 순서와 승패를 잘 정해서 시청률의 총합을 최대화한다면 어느 정도까지 시청률의 합이 커질 수 있는지가 궁금해졌다.

경기의 순서와 승패를 잘 정해, 시청률의 합의 최댓값을 구해 보고, 경기가 어떻게 진행되어야 하는지 정해 보자.

 

유형 : MST + DFS

 

접근 방식

• N - 1번의 경기를 진행하면서 시청률의 합이 최대가 된다는 것에서 MST를 구해야 한다.
• 크루스칼을 통해 구한 값이 시청율의 합이다.
• 크루스칼을 구하면서 사용되는 간선들을 바탕으로 그래프를 만들자
• 승자는 떠나고 패자는 남는다는 것이 의미하는 바는 한 지점에서 출발해서 승자가 된 사람을 다시 거치지 않고 모든 지점을 방문할 수 있다는 뜻이다. 즉 트리 형태에서 리프 노드부터 승자로 지정해서 (부모 : 패자, 자식 : 승자) 형태로 출력하면 된다.

 

코드

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

public class BOJ_14574_헤븐스_키친 {

    static int n;
    static int[] root;
    static int[][] cook;
    static ArrayList<Integer>[] graph;
    static boolean[] v;
    static StringBuilder sb = new StringBuilder();

    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());
        root = new int[n+1];
        cook = new int[n+1][2];
        v = new boolean[n+1];

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

        for(int i = 1 ; i <= n ; i++) {
            root[i] = i;

            st = new StringTokenizer(br.readLine()," ");

            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            cook[i][0] = p;
            cook[i][1] = c;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (x,y) -> y[2] - x[2]
        );

        for(int i = 1 ; i < n ; i++) {
            for(int j = i + 1 ; j <= n ; j++) {
                pq.add(new int[]{i,j,getValue(i,j)});
            }
        }

        long result = 0;
        int count = 0;

        while(!pq.isEmpty()) {
            int[] tmp = pq.poll();

            if(find(tmp[0]) != find(tmp[1])) {
                union(tmp[0],tmp[1]);
                result += tmp[2];
                graph[tmp[0]].add(tmp[1]);
                graph[tmp[1]].add(tmp[0]);
                count++;
            }

            if(count == n - 1)
                break;
        }

        v[1] = true;
        go(1);
        System.out.println(result);
        System.out.print(sb);

        br.close();
    }

    static void go(int c) {
        for(int next : graph[c]) {
            if(!v[next]) {
                v[next] = true;
                go(next);
                sb.append(c).append(" ").append(next).append("\n");
            }
        }
    }

    static int getValue(int idx1, int idx2) {
        return (cook[idx1][1] + cook[idx2][1]) / Math.abs(cook[idx1][0] - cook[idx2][0]);
    }

    static int find(int x) {
        if(x == root[x])
            return root[x];

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

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

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