[JAVA] 백준 10486 - Trapezoid Walkway

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

Back Porch에서 시작해 Gazebo로 끝나는 길을 사다리꼴 모양의 타일을 이어 만들 때, 이어 붙여지는 변의 길이가 일치하도록 길을 만들어나가되, 가격이 가장 싸게 만드는 방법을 찾는 문제이다.(1제곱센티미터 당 2 센트)

 

N개의 줄에 a,b,h가 주어지고, 그 다음줄에 Back Porch와 Gazebo의 변의 길이가 각각 주어진다. 

만약 Back Porch와 Gazebo의 길이가 같으면 0을 반환하고, 아닐 경우는 변의 길이, 높이, 넓이, 누적높이를 가지는 클래스를 제네릭타입으로 가지는 우선순위큐를 이용해 Back Porch에서 출발해 Gazebo로 도착하는 누적 넓이의 최솟값을 구했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        while((t = par(br.readLine()))!=0){
            List<Stone> list = new ArrayList<>();
            for (int i = 0; i < t; i++) {
                int[] temp = getArray(br.readLine());
                list.add(new Stone(temp[0],temp[1],temp[2]));
                list.add(new Stone(temp[1],temp[0],temp[2]));
            }
            int[] info = getArray(br.readLine());
            int start = info[0];
            int end = info[1];
            if(start==end) {System.out.printf("%.2f",0d); continue;}
            int count = (int) list.stream().mapToInt(x -> x.a).distinct().count();
            List<Integer> nodeList = list.stream().mapToInt(x -> x.a).distinct().boxed().collect(Collectors.toUnmodifiableList());
            boolean[] visited = new boolean[count];
            PriorityQueue<Stone> pq = new PriorityQueue<>();

            list.stream().filter(x -> x.a==start).forEach(x -> x.totalArea = x.area);
            list.stream().filter(x -> x.a==start).forEach(pq::offer);
            while(!pq.isEmpty()){
                Stone st = pq.poll();
                int a = st.a;
                int b = st.b;
                if(visited[nodeList.indexOf(a)]&&visited[nodeList.indexOf(b)] ) continue;
                visited[nodeList.indexOf(a)] = true;
                visited[nodeList.indexOf(b)] = true;
                for (int i = 0; i < list.size(); i++) {
                    Stone stone = list.get(i);
                    if(stone.a==b && !visited[nodeList.indexOf(stone.b)]){
                        stone.totalArea = st.totalArea + stone.area;
                        pq.offer(stone);
                    }
                }
            }
            double min = Integer.MAX_VALUE;
            for (int i = 0; i < list.size(); i++) {
                if(list.get(i).b==end){
                    min = Math.min(min,list.get(i).totalArea*2/100);
                }
            }
            System.out.printf("%.2f",min);
            System.out.println();
        }
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Stone implements Comparable<Stone>{
    int a;
    int b;
    int h;
    double area;
    double totalArea = Integer.MAX_VALUE;
    Stone(int a, int b, int h){
        this.a = a;
        this.b = b;
        this.h = h;
        area = (double)(a+b)*h/2;
    }

    @Override
    public int compareTo(Stone o) {
        return Double.compare(this.totalArea,o.totalArea);
    }
}