[프로그래머스 Lv. 2] 당구 연습

문제

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

접근

위의 사진에서 원 쿠션을 통한 (7,7)과 (3,7)의 거리와 (3,7)과 (7, 13)의 거리는 같다.
이 방법을 이용해 문제에 접근한다.

1. 현재 공의 위치에서 상하좌우로 벽에 닿을 때의 좌표를 구한다.
2. 같은 라인에 공이 있는지 체크를 한다.
3. 목표로 해야하는 공들의 위치 (balls)를 위에서 구한 좌표 기준으로 선대칭을 한다.
   공식은 현재 좌표 + abs(대칭이동 기준좌표 - 현재 좌표) * 2
   3-1. 왼쪽 오른쪽 벽의 좌표를 기준으로 대칭이동을 할 경우 y축을 기준으로 대칭이동을 시킨다.
   3-2. 위 아래 벽의 좌표를 기준으로 대칭이동을 할 경우 x축을 기준으로 대칭이동을 시킨다.
4. 모든 거리를 구한 뒤 최소 값을 answer에 넣어준다

Code

from collections import defaultdict


def solution(m, n, startX, startY, balls):
    def is_same(ball, x, y, dir):
        while True:
            y += dy[dir]
            x += dx[dir]

            if y <= 0 or y >= n or x <= 0 or x >= m:
                return False
            if [x, y] == ball:
                return True

    dy, dx = [1, -1, 0, 0], [0, 0, -1, 1]  # U, D, L R
    directions = ['U', 'D', 'L', 'R']
    answer = []
    direction_dict = defaultdict(int)

    for i in range(4):
        dir = directions[i]
        cy, cx = startY, startX
        while True:
            cy += dy[i]
            cx += dx[i]

            if cy <= 0 or cy >= n or cx <= 0 or cx >= m:
                direction_dict[dir] = (cx, cy)
                break

    for ball in balls:
        feasible = []
        for direction in directions:
            if direction == 'U' and not is_same(ball, startX, startY, 0):
                flip = (ball[0], ball[1] + (direction_dict[direction][1] - ball[1]) * 2)
                feasible.append((flip[0] - startX) ** 2 + (flip[1] - startY) ** 2)
            elif direction == 'D' and not is_same(ball, startX, startY, 1):
                flip = (ball[0], ball[1] + (direction_dict[direction][1] - ball[1]) * 2)
                feasible.append((flip[0] - startX) ** 2 + (flip[1] - startY) ** 2)
            elif direction == 'L' and not is_same(ball, startX, startY, 2):
                flip = (ball[0] + (direction_dict[direction][0] - ball[0]) * 2, ball[1])
                feasible.append((flip[0] - startX) ** 2 + (flip[1] - startY) ** 2)
            elif direction == 'R' and not is_same(ball, startX, startY, 3):
                flip = (ball[0] + (direction_dict[direction][0] - ball[0]) * 2, ball[1])
                feasible.append((flip[0] - startX) ** 2 + (flip[1] - startY) ** 2)

        answer.append(min(feasible))
    return answer

여담

웬만한 프로그래머스 레벨2 문제보다 어려운 것 같다.