문제

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

풀이

아이디어

어차피 (startX, startY)와 완전히 동일한 공의 위치는 없을 것이므로, 다음과 같이 경우를 나눈다.

1. startX == 공의 x좌표인 경우
   • x=0에 튕기는 거리 or x=m에 튕기는 거리 중 최소
   • y=0이나 y=n에 스타트공을 튕기는 거리 중 최소
   • 위 두 경우 중 최솟값을 선택한다.
2. startY == 공의 y좌표인 경우
   • y=0에 튕기는 거리 or y=n에 튕기는 거리 중 최소
   • x=0이나 x=m에 스타트공을 튕기는 거리 중 최소
   • 위 두 경우 중 최솟값을 선택한다
3. 공의 x, y가 시작점과 아예 겹치지 않는 경우
   • 4개의 벽(x=0, y=0, x=m, y=n)에 싹 다 대칭시켜보면서 그 중 최솟값 선택

이때, 다음과 같은 상황에서 공이 이동한 거리를 어떻게 구할 수 있을까?

고등학교 수학을 한 지 너무 오래되서 나도 뻘짓하고 있었는데.... 바로 "대칭"을 이용해서 구하는 것이다. 진짜 수학 다 까먹었네...

이렇게 대칭시켜주면 A와 B'의 좌표 사이의 거리만 구해서 이 직선거리의 제곱만 구하면 되므로 상당히 간단해진다. (입사각 반사각 동일해지는 y좌표 찾지 말고...)

코드

def solution(m, n, startX, startY, balls):
    answer = []
    reflectX, reflectY = 0, 0
    for x, y in balls:
        candidates = []
        #startX와 x가 같은 경우, 0과 m 중 가까운 세로벽에 부딪히게 한다.
        if startX == x:
            reflectX = 0 if x < m/2 else m
            reflectY = (startY + y) / 2
            candidates.append(((x-reflectX)**2 + (y - reflectY)**2) * 4)
            if startY >= y:
                candidates.append((n-startY + n-y)**2)
            else:
                candidates.append((startY + y)**2)
            answer.append(min(candidates))
        #startY와 y가 같은 경우, 0과 n 중 가까운 가로벽에 부딪히게 한다.
        elif startY == y:
            reflectY = 0 if y < n/2 else n
            reflectX = (startX + x) / 2
            candidates.append(((x-reflectX)**2 + (y - reflectY)**2) * 4)
            if startX < x:
                candidates.append((startX + x)**2)
            else:
                candidates.append((m-startX + m-x)**2)
            answer.append(min(candidates))
        #startX와 x가 다르고, startY와 y도 다 다른 경우
        else:
            #세로벽 대칭
            candidates.append((startX+x)**2 + (startY-y)**2)
            #가로벽 대칭
            candidates.append((m+m-startX-x)**2 + (startY-y)**2)
            #윗벽 대칭
            candidates.append((startX-x)**2 + (n-startY+n-y)**2)
            #아랫벽 대칭
            candidates.append((startX-x)**2 + (y+startY)**2)
            answer.append(min(candidates))
    return answer