[프로그래머스] 당구 연습 - JAVA

🔗 문제

 

👨🏻‍💻 풀이 및 코드

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

입사각과 반사각이 같은 경우는 다음과 같이 네 방향으로 공을 대칭 이동 할 수 있습니다.

예를 들어, 빨간 타겟공을 1번 위치로 대칭이동을 한다면, 파란 시작 공과 1번 공과의 거리가 시작 공에서 벽을 맞고 빨간 공으로 돌아온 거리와 같기 때문에 해당 거리가 최단 거리 입니다.

 

즉, 네 방향으로 대칭 이동 시킨 후, 그 중 시작 공과의 거리가 가장 짧은 값을 리턴하면 됩니다.

 

단, 주의할 점이 있습니다.

예시와 같이 3번 방향으로 대칭 이동을 시키는 경우 벽에 맞기 전에 타겟 공을 먼저 맞기 때문에 이와 같이 일직선으로 놓인 방향은 제외시켜야 합니다.

 

대칭 이동하는 공의 좌표를 수식으로 바꾸면 다음과 같습니다.

 

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int startX, int startY, int[][] balls) {
        int[] answer = new int[balls.length];
        Point start = new Point(startX, startY);
        Point board = new Point(m, n);
        for(int i=0; i<balls.length; i++) {
            List<Point> nballs = getBallList(board, start, new Point(balls[i][0], balls[i][1]));
            int res = Integer.MAX_VALUE;
            for(Point nball : nballs) {
                res = Math.min(res, calculateDistance(start, nball));
            }
            answer[i] = res;
        }
        return answer;
    }
    
    List<Point> getBallList(Point board, Point start, Point ball) {
        List<Point> nballs = new ArrayList<>();
        //4방향
        //위 - 1
        if(!(ball.x == start.x && start.y < ball.y)) {	//일직선상의 아니라면
            nballs.add(new Point(ball.x, board.y + (board.y - ball.y)));	// 대칭이동
        }
        //아래 - 2
        if(!(ball.x == start.x && start.y > ball.y)) {
            nballs.add(new Point(ball.x, -1*ball.y));
        }
        // 우 - 3
        if(!(start.x < ball.x && start.y == ball.y)) {
            nballs.add(new Point(board.x + (board.x-ball.x), ball.y));
        }
        // 좌 - 4
        if(!(ball.x < start.x && start.y == ball.y)) {
            nballs.add(new Point(-1*ball.x, ball.y));
        }
        
        return nballs;
    }
    
    // 두 점 사이의 거리를 계산
    int calculateDistance(Point start, Point ball) {
        return (int)Math.pow(start.x-ball.x, 2) + (int)Math.pow(start.y-ball.y, 2);
    }
    
    class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}