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

1. 문제 정의

 당구대가 있다고 하고, 당구 볼의 시작 점인 startX와 startY가 주어지며, 목표점의 x좌표와 y좌표가 담긴 리스트들이 주어진다.

이 때 시작점으로 부터 원쿠션으로 진행하여 x,y좌표까지 도달할 수 있는 최소거리를 구하는 것이 문제. (입사각과 반사각은 같다.)

 

2. 내가 한 시도

 처음에는 입사각 반사각이 같다는 말에 조금 혼란이 있었지만, 결국에 1쿠션을 한다는 것은 그 쿠션을 하는 축을 기준으로 한 개의 점을 대칭시켜 일직선으로 연결되는 것이 두 점사이의 최소 값이라는 것 깨닫는 것이 핵심이었던 문제인 것 같다.

 직선거리가 최솟값인 것을 깨달았다면 각 면 별로 최솟값을 구해서 그 중에 가장 적은 값을 최솟값으로 저장하면 해결되는 문제였다. 다만 두 점의 x좌표가 같거나 y좌표가 같을때에는 한 면이 쿠션이 불가능하기 때문에 그 최솟값을 제외한 나머지 값들 중에서 최솟값을 구해야 했다.

 

3.  코드

/**
 * 프로그래머스 LV2
 * 당구게임
 * 접근 방법: 각각 쿠션을 하는 축을 기준으로 대칭이동을 했을 때 직선 == 쿠션을 할 경우 최솟값이라는 것을 바탕으로 구현.
 */
public class Solution {

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

        for (int i = 0; i < balls.length; i++) {
            int[] ball = balls[i];
            int compare = compare(m, n, start, ball);
            answer[i] = compare;
        }
        return answer;
    }

    public int compare(int m, int n, int[] start, int[] end) {
        int min = Integer.MAX_VALUE; // 최종적으로 구할 최솟값

        int endX = end[0];
        int endY = end[1];

        /*
         * 위쪽으로 쿠션 로직
         */
        if (!(start[0] == end[0] && start[1] < end[1])) { // x좌표가 같고, startY보다 endY가 클 경우는 위쪽으로 쿠션을 하지 못함.
            int startX = start[0];
            int startY = n + n - start[1];

            int distance = getDistance(startX, startY, endX, endY);
            min = Math.min(min, distance);
        }

        /*
         * 아래쪽으로 쿠션 로직
         */
        if (!(start[0] == end[0] && start[1] > end[1])) { // x좌표가 같고, startY가 endY보다 클 경우는 아래쪽으로 쿠션을 하지 못함.
            int startX = start[0];
            int startY = start[1] * -1;

            int distance = getDistance(startX, startY, endX, endY);
            min = Math.min(min, distance);
        }

        /*
         * 왼쪽으로 쿠션 로직
         */
        if (!(start[1] == end[1] && start[0] > end[0])) { // y좌표가 같고, startX가 endX보다 클 경우는 왼쪽으로 쿠션을 하지 못함.
            int startX = start[0] * -1;
            int startY = start[1];

            int distance = getDistance(startX, startY, endX, endY);
            min = Math.min(min, distance);
        }

        /*
         * 오른쪽으로 쿠션 로직
         */
        if (!(start[1] == end[1] && start[0] < end[0])) { // y좌표가 같고, startX보다 endX가 클 경우는 오른쪽으로 쿠션을 하지 못함.
            int startX = m + m - start[0];
            int startY = start[1];

            int distance = getDistance(startX, startY, endX, endY);
            min = Math.min(min, distance);
        }

        return min;
    }

    public int getDistance(int x1, int y1, int x2, int y2) {
        return (int) (Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }

}

4. 회고

 입사각과 반사각이라는 단어에 현혹되지 않고, 결국에는 최솟값은 직선거리라는 것을 깨닫는다면 대칭을 이용해서 쉽게 접근할 수 있었던 문제였다.

 역시 알고리즘 문제와 수학 문제는 푸는 방법을 떠올리는 것이 제일 중요한 것 같다. 푸는 방법을 떠올릴 수만 있다면, 문제의 난이도는 생각이 안 나는 것 보다 훨씬 낮아지는 느낌이다. 

 

참조

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