[programmers/js] 당구 연습

당구 연습

https://school.programmers.co.kr/learn/courses/30/lessons/169198#

문제 설명

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

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

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

풀이

1. 벽 반사를 생각하기 어려우니까, 거꾸로 벽을 기준으로 목표점을 반사시키고, 큐볼과의 직선 거리를 모두 구해서 최솟값을 찾는 것.

결국 반사를 통해 값을 찾는 것은 반사 벽을 기준으로 목표 Ball을 뒤집어 직선 거리를 구하는 것과 같습니다.

function solution(m, n, startX, startY, balls) {
    const answer = [];
    
    for (const [x, y] of balls) {
        const candidates = [];
        
        // 각 벽에 반사된 값
        const reflections = [
            [x, -y], // 아래쪽 벽
            [x, 2 * n - y], // 위쪽 벽
            [-x, y], // 왼쪽 벽
            [2 * m - x, y], // 오른쪽 벽
        ];
        for (const [rx, ry] of reflections) {            
            const dx = rx - startX;
            const dy = ry - startY;
            const dist2 = dx * dx + dy * dy;
            
            if (y === startY) {
                if ((startX < x && x < m) && rx === 2 * m - x) continue;
                if ((0 < x && x < startX) && rx === -x) continue;
            }
            
            if (x === startX) {
                if ((startY < y && y < m) && ry === 2 * n - y) continue;
                if ((0 < y && y < startY) && ry === -y) continue;
            }
            candidates.push(dist2);
        }
        
        answer.push(Math.min(...candidates));
    }
    return answer;
}

2. 4개의 벽을 다 거쳐서 최솟갑 구하기

위 문제풀이를 다시 생각해 보면 결국 4개의 벽을 거치는 값 중 가장 작은 값을 구하는 문제입니다.

이때, 반드시 원 쿠션을 해야 하기에 벽에 부딪히기 전, 목표 Ball을 만나는 경우는 제외해 줍니다.

function solution(m, n, startX, startY, balls) {  
    const answer = [];
    for (const [x, y] of balls) {
        const dist = [];
        
        // y값이 같을 때, 왼쪽 벽을 못 쓰는 경우가 아니라면 -> 왼쪽 벽 사용
        if (!(y === startY && x < startX)) dist.push((x + startX) ** 2 + (y - startY) ** 2);
        // y값이 같을 때, 오른족 별을 못 쓰는 경우가 아니라면 -> 오른쪽 벽 사용
        if (!(y === startY && x > startX)) dist.push((2 * m - startX - x) ** 2 + (y - startY) ** 2);
        // 위쪽 사용
        if (!(x === startX && y > startY)) dist.push((x - startX) ** 2 + (2 * n - y - startY) ** 2);
        // 아래 벽 사용
        if (!(x === startX && y < startY)) dist.push((x - startX) ** 2 + (y + startY)**2);
        
        answer.push(Math.min(...dist));
    }
    return answer;
}