paizaキャンペーン問題「怪盗813からの挑戦状」を解いてみた

問題を解いたら、抽選でAmazonギフト券とかお肉とかが貰えるとのことで、チャレンジしてみた。
https://paiza.jp/poh/phantom_thief

問題

お宝の場所の情報は怪盗の居る場所を 0, 0 として N 個 のお宝の x, y 座標がメートル単位で書かれています。
各座標間は直線で移動します。0, 0 の位置からスタートし、可能な限り短いルートでお宝を全て盗むルートを出力してください。

考え方

原点から一番近い座標を出力して、その座標からまた一番近い座標を出力して…を繰り返せば、短いルートで進めるのでは？と思って、解いてみた。

解答をブログとかに書いてもいいと書いてあったので、以下に掲載。

提出コード

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine().replaceAll(" ","");
        int itemCount = Integer.parseInt(firstLine);

        ArrayList<Point> pointList = new ArrayList<Point>();

        //標準入力から座標リストを作成する
        for(int i = 0; i < itemCount ; i++){
            String[] line = sc.nextLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            pointList.add(new Point(x,y));
        }

        Point originPoint = new Point(0,0);
        while(pointList.size() > 0){
            int minDistance = Integer.MAX_VALUE;
            Point minDistancePoint = new Point();

            //基準点から一番距離の近い座標を座標リストから取得する
            for(Point getPoint : pointList){
                int tmpDistance = getDistance(originPoint,getPoint);
                if(minDistance > tmpDistance){
                    minDistance = tmpDistance;
                    minDistancePoint = getPoint;
                }
            }
            //座標位置を表示する
            minDistancePoint.output();
            //基準点を変更する
            originPoint = minDistancePoint;
            //座標リストから座標を削除する
            int index = pointList.indexOf(minDistancePoint);
            pointList.remove(index);
        }
    }

    //二点の座標間の距離を求める
    public static int getDistance(Point p1, Point p2) {
            double x1 = p1.x;
            double y1 = p1.y;
            double x2 = p2.x;
            double y2 = p2.y;

        double distance = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        return (int) distance;
    }

}

//座標クラス
class Point{
    int x;
    int y;

    public Point(){
        this.x = 0;
        this.y = 0;
    }

    public Point(int x , int y){
        this.x = x;
        this.y = y;
    }

    public void output(){
        System.out.println(x + " " + y);
    }
}

結果

こちら。最適解じゃなかったようだ。
https://paiza.jp/poh/phantom_thief/result/a8a222d8

最適解を求めるには？

ちょっと調べたところ、巡回セールスマン問題と呼ばれる問題っぽい。
（最初の座標に戻らなくていいので、少し違う？）

今回私が解いた方法は「欲張り法」というアルゴリズムのようだ。

巡回セールスマン問題を解くためのアルゴリズムには「2-opt法」「山登り法」「焼きなまし法」などがあり、これらを使うともっと最適解に近くなるようだけど、難しそうなので諦めた。