23.04.18 파이썬 코딩 퀴즈#226 당구 연습(프로그래머스 스쿨)

이번 문제는 당구 연습 문제이다.

내가 좋아하는 당구 인데, 이걸 문제로 보니 일단 설명부터 머리가 아프다.

먼저 주어지는 당구대의 길이는 가로m , 세로 n 이고 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY 가 주어진다. 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표 쌍이 balls 에 주어진다.

이제 머쓱이는 한번 벽에 맞춘 다음 목표로 하는 공들을 정확하게 맞추어야 하는데, 여기서 입사각과 반사각이 등장한다.

입사각은 현재 공 위치에서 벽으로 진입하는 각도를 의미하고, 반사각은 그 공이 벽을 맞고 튀어나가는 각도를 의미하며, 입사각과 반사각은 동일하다. 반드시 벽을 한번 거치고 공을 맞추어야 하며, 이렇게 공을 맞추기 위해 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 해야 한다.

위 그림이 바로 입사각과 반사각이 동일함을 나타내는 설명이다.

하지만 공이 당구대의 꼭짓점에 맞을 경우, 정확히 같은 각도로 튀어 나온다. 위 그림은 45도의 입사각을 가지기 때문에 정확히 45도의 반사각을 가지게 되고, 다시 제자리로 돌아오게 된다.

만약 다른 각도의 입사각이라면, 그 각도를 다시 반사각을 가져 위 그림과 같은 형태로 공이 움직인다.

특별한 점은 없어 보인다. 다만 공의 처음 위치와 맞춰야 하는 공의 위치가 동일한 경우는 주어지지 않는다.

입출력 예를 통해 좀 더 자세히 살펴보자.

먼저 첫번째 타겟인 [7,7]을 살펴보자.

문제 설명에도 그림이 있지만, 뭔가 답만 덜렁 있어서 따로 그림을 그려보았다.

먼저 현재 위치에서 타겟까지 벽을 한번 맞추고 갈 수 있는 경우는 총 3가지 이다. (위쪽벽, 아래쪽 벽, 왼쪽 벽)

그 중에서 최단 거리를 선택해야 한다면, 현재 위치에서 벽까지 가는 최단 거리를 선택해야 한다.

그리고 이때 필요한게 바로 피타고라서의 정의 이다.... 

먼저 왼쪽 벽을 이용하게 된다면, 벽으로 이동거리 3 + 다시 공까지 이동거리 7 해서 10이 되고 제곱을 계산하기에 100이 된다.

위쪽 벽을 이용하게 된다면, 정확히 이등변 삼각형을 그리게 되고, 이를 둘로 나눠서 피타고라스 공식을 적용하면 각 변의 길이는 루트53이 된다. 따라서 총 이동 거리드 2루트53이므로, 이를 제곱하면 216이 된다.

마지막으로 아래쪽 벽을 이용하게 되면, 각 변의 길이는 루트13이고, 두변의 길이 합을 제곱하면 52이 된다.

 

2번째 좌표는 1번째 좌표와 비슷하기에 패스하고, 3번째 좌표 [7,3]를 살펴보자.

각 벽을 기준으로 직각 삼각형을 그린 모습이다... 뭔가 굉장히 난해하다... 심지어 벽에 맞는 좌표값이 정확히 정수로 떨어지지 않는다.

해설에서는 별다른 설명 없이 해당 길이 최소 이동 거리이고, 그 이동 거리의 제곱이 116이라고만 설명 되어 있다.

당구를 안쳐본 사람이라면 해당 문제를 가지고 굉장히 씨름을 할 것처럼 보인다...

문제를 좀 더 쉽게 접근하기 위해서는 우선 전달받은 보드를 확장해서 생각해야 한다.

 

보드를 확장하고, 벽을 기준으로 타겟을 대칭이동 시킨 모습이다. 당구에서는 기본적으로 빈쿠션 치기를 할 때 공식처럼 사용되는 방식이다. 이제 이동거리를 구해야할 방법이 정해졌다. 즉 대칭 이동시킨 공의 좌표와 현재 공의 위치 좌표를 기준으로 직각 삼각형을 만들게 되면 높이는 10, 밑변은 4가 된다. 따라서 총 이동 거리는 116이 된다.

그리고 이를 생각하면 꼭지점을 보내서 공을 맞추는 것보다, 벽을 이용하는게 더 이동거리가 짧다는 결론도 나온다.

그 이유는 꼭지점을 이용하면 더 큰 직각삼각형을 2번 이용하기 때문이다.

 

이제 이를 코드를 이용해서 풀어보자.

먼저 전달받은 좌표 기준으로 up, down, left, right 대칭 좌표를 구해준다. 이는 조금만 머리를 써보면 충분히 수학적으로 표현할 수 있다.

이제 3가지 조건에 의해 확인해야 할 값이 갈리게 된다.

먼저 x 좌표가 같은 경우라면, 좌우 대칭점을 기본적으로 확인해야 한다. 그 이후 타겟공이 현재 공보다 위에 있는 경우라면 아래벽을, 아래에 있는 경우라면 윗 벽을 기준으로 하는 대칭점을 확인하여 피타고라스 공식을 대입한다.

그 다음 y 좌표가 같은 경우라면, 이제는 상하 대칭점을 먼저 확인하고, 그 이후 타겟의 위치에 따라 왼쪽 오른쪽 벽 중 하나를 선택하여 계산하다.

그리고 두 점의 x,y 좌표가 서로 일치하지 않는 경우라면 상하좌우 모두 확인이 필요하다.

위 그림에서처럼 상하, 좌우는 각각 한변을 공유 하므로 서로 쌍으로 묶어서 다른 변의 길이가 최소인 것만 계산해 주면 된다.

그리고 이렇게 나온 값들중 최솟값을 answer에 담아주면 된다.