[Java] Lv.2 당구 연습

문제

 

문제 설명
프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 
하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 
당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고,
벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 
당구공의 위치가 담긴 리스트를 건네줬습니다.

리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다.
머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 
이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은,
머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과
머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 
그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. 
"원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때,
각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 
만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다.

공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 
공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

제한사항
3 ≤ m, n ≤ 1,000
0 < startX < m
0 < startY < n
2 ≤ balls의 길이 ≤ 1,000
balls의 원소는 [a, b] 형태입니다.
a, b는 머쓱이가 맞춰야 할 공이 놓인 좌표를 의미합니다.
0 < a < m, 0 < b < n
(a, b) = ( startX, startY )인 입력은 들어오지 않습니다.

프로그래머스

 

문제 풀이

반사각을 계산하면서 풀려면 생각보다 어렵다.

반사각을 쭉 펴서 직선으로 구해서 길이를 계산하는 방식으로 구해야한다.

공이 어디에 있든지 결국 4방향(상, 하, 좌, 우)로 공을 치게 된다.

이 중 공이 x혹은 y축에 대해 선대칭일 때 벽보다 공에 먼저 맞는 경우(원 쿠션이 아닌 경우)를 제외한 나머지 경우의 직선길이를 구한다. 이 후 이 직선 길이중 가장 짧은 것을 구하면 된다.

 

예를 들어 아래와 같은 형태로 공이 있다고 했을 때 (파란공 칠 공, 빨간 공 맞힐 공)

오른쪽으로 치는 (원 쿠션이 안되는 경우)를 제외하면 3 방향으로 쳐서 공을 맞히는 경우가 있을 것이다.

이 경우의 수를 반사각을 기준으로 직선으로 만들어서, 즉 맞힐 공의 대칭 위치를 구해서 그 직선의 길이를 구하는 것이다.

예시 하나를 더 보여주겠다. 이 경우는 위로 치는 경우를 제외한 나머지의 대칭 위치 값을 구해서 그 직선 길이를 구하고 이 중 짧은 것을 구하면 된다.

자바 코드

import java.util.*;

class Solution {
    private static class Point{
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int[] solution(int m, int n, int startX, int startY, int[][] balls) {
        int[] answer = new int[balls.length];

        // 보드 크기
        Point boardEndPos = new Point(m, n);
        // 칠 공의 위치
        Point startPos = new Point(startX, startY);

        for (int i = 0; i < balls.length; i++) {
            // 맞출 공의 위치
            int[] ball = balls[i];

            // 칠 공과 맞출 공의 위치를 기반으로 네 방향의 대칭 위치 구하기
            List<Point> transBall = symmetricTransposition(boardEndPos, startPos, new Point(ball[0], ball[1]));

            int minDistance = Integer.MAX_VALUE;
            // 각 방향의 포인트를 이용하여 이동 길이를 구한다.
            for (Point point : transBall) {
                int dis = calculationDistance(startPos, point);
                
                // 이동 길이 중 가장 짧은 것을 구한다.
                minDistance = Math.min(minDistance, dis);
            }

            answer[i] = minDistance;
        }


        return answer;
    }

    // 맞힐 공 위치 대칭 이동 시키기
    private static List<Point> symmetricTransposition(Point boardEnd, Point start, Point ball) {
        List<Point> syms = new ArrayList<>();

        // 4 개의 방향으로 대칭이동
        // 선 대칭일 때, 벽보다 공에 먼저 맞는 경우 제외(원 쿠션이 아니게 되기 때문)
        // 아래로 치기, 같은 x축, 칠 공이 y축이 더 높을 경우 제외
        if(!(start.x == ball.x && start.y > ball.y)) 
            syms.add(new Point(ball.x, ball.y * -1));
        // 위로 치기, 같은 x축, 칠 공이 y축이 더 낮을 경우 제외
        if(!(start.x == ball.x && start.y < ball.y)) 
            syms.add(new Point(ball.x, boardEnd.y + (boardEnd.y- ball.y)));
        // 오른쪽으로 치기, 같은 y축, 칠 공이 x축이 더 낮을 경우 제외
        if(!(start.y == ball.y && start.x < ball.x)) 
            syms.add(new Point(boardEnd.x + (boardEnd.x - ball.x), ball.y));
        // 왼쪽으로 치기, 같은 y축, 칠 공이 x축이 더 높을 경우 제외
        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);
    }
}