프로그래머스 - 당구 연습(Java)

구현 문제입니다.

 

이 문제를 해결하기 위해서는 한 가지 수학적 아이디어가 필요합니다.

 

입사각과 반사각이 같으면, 아래 그림과 같이 네 방향으로 대칭 이동을 할 수 있습니다.

 

즉, 공(ball)을 네 방향으로 대칭이동 시켜 최소 직선 거리를 구하면 됩니다.

 

주의해야할 점이 있습니다.
그림의 2번은 불가능합니다.

2번과 같이 파란색 공이 움직이면 벽보다 빨간색 공에 먼저 맞기 때문입니다.

때문에 두 공이 선 대칭 일 경우, 움직이는 공이 벽보다 다른 공에 먼저 맞는 경우를 제외해야 합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public static int[] solution(int m, int n, int startX, int startY, int[][] balls) {
        int[] answer = new int[balls.length];

        Point border = new Point(m, n);
        Point start = new Point(startX, startY);

        for (int i = 0; i < balls.length; i++) {
            int[] ball = balls[i];

            List<Point> transBall = symmetricTransposition(border, start, new Point(ball[0], ball[1]));

            int minDistance = Integer.MAX_VALUE;
            for (Point point : transBall) {
                int dis = calculationDistance(start, point);

                minDistance = Math.min(minDistance, dis);
            }

            answer[i] = minDistance;
        }


        return answer;
    }

    private static List<Point> symmetricTransposition(Point bord, Point start, Point ball) {
        List<Point> syms = new ArrayList<>();

        // 4 개의 방향으로 대칭이동
        // 선 대칭일 때, 벽보다 공에 먼저 맞는 경우 제외
        if(!(start.x == ball.x && start.y > ball.y)) syms.add(new Point(ball.x, ball.y * -1));
        if(!(start.x == ball.x && start.y < ball.y)) syms.add(new Point(ball.x, bord.y + (bord.y- ball.y)));
        if(!(start.y == ball.y && start.x < ball.x)) syms.add(new Point(bord.x + (bord.x - ball.x), ball.y));
        if(!(start.y == ball.y && start.x > ball.x)) syms.add(new Point(ball.x * -1 , ball.y));

        return syms;
    }

    private static int calculationDistance(Point start, Point ball){
        int bigX = Math.max(start.x, ball.x);
        int smallX = Math.min(start.x, ball.x);
        int bigY = Math.max(start.y, ball.y);
        int smallY = Math.min(start.y, ball.y);

        return (int)Math.pow(bigX - smallX, 2) + (int)Math.pow(bigY - smallY, 2);
    }

    private static class Point{
        int x, y;

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