[BOJ] 14574 헤븐스 키친 (JAVA)

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

14574번: 헤븐스 키친

MST를 만든 다음, DFS로 승 패를 정하면 되는 문제입니다.

 

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

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, P, C, cnt;
    static long sum;
    static int[] parent;
    static boolean[] visited;
    static Cook[] cooks;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) throws Exception {

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N + 1];
        cooks = new Cook[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine(), " ");
            P = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            cooks[i] = new Cook(P, C);
        } // end of input

        make();
        PriorityQueue<Battle> pq = new PriorityQueue<>();

        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                Cook c1 = cooks[i];
                Cook c2 = cooks[j];
                int ratio = (c1.c + c2.c) / Math.abs(c1.p - c2.p);
                pq.offer(new Battle(i, j, ratio));
            }
        }

        while (!pq.isEmpty()) {
            Battle b = pq.poll();
            if (union(b.cook1, b.cook2)) {
                sum += b.ratio;
                list[b.cook1].add(b.cook2);
                list[b.cook2].add(b.cook1);
                if (++cnt == N - 1) break;
            }
        }

        sb.append(sum).append("\n");

        dfs(1);

        System.out.print(sb);

    }

    static void dfs(int now) {
        visited[now] = true;
        for (int to : list[now]) {
            if (!visited[to]) {
                dfs(to);
                sb.append(now).append(" ").append(to).append("\n");
            }
        }
    }

    static boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return false;

        if (a < b) parent[b] = a;
        else parent[a] = b;
        return true;
    }

    static int find(int a) {
        if (parent[a] == a) return a;
        return find(parent[a]);
    }

    static void make() {
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }

    static class Cook {
        int p, c;

        public Cook(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    static class Battle implements Comparable<Battle> {
        int cook1, cook2, ratio;

        public Battle(int cook1, int cook2, int ratio) {
            this.cook1 = cook1;
            this.cook2 = cook2;
            this.ratio = ratio;
        }

        @Override
        public int compareTo(Battle o) {
            return o.ratio - this.ratio;
        }
    }
	
}