[프로그래머스] 당구연습 (Python)

사이트 링크: https://school.programmers.co.kr/learn/courses/30/lessons/169198

프로그래머스

 

 

문제

프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

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

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

위 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

 

위 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

 

 

 

입출력

 

 

 

코드

 

 

def solution(m, n, startX, startY, balls):
    answer = []
    start = [startX,startY]
    for i in range(len(balls)):
        end = [balls[i][0], balls[i][1]]
        distance = 10**10
        temp = []
        if start[0]!=end[0] or start[1] > end[1]: 
            temp.append(abs(start[0]-end[0])**2 + abs(2*n-start[1]-end[1])**2)  #우
        if start[0]!=end[0] or start[1] < end[1]: 
            temp.append(abs(start[0]-end[0])**2 + abs(start[1]+end[1])**2)      #좌
        if start[1]!=end[1] or start[0] < end[0]: 
            temp.append(abs(start[0]+end[0])**2 + abs(start[1]-end[1])**2)      #상
        if start[1]!=end[1] or start[0] > end[0]: 
            temp.append(abs(2*m-start[0]-end[0])**2 + abs(start[1]-end[1])**2)  #하
        for dist in temp:
            if dist < distance:
                distance = dist
        answer.append(distance)
    return answer

 

 

 

 

문제풀이

복잡한 알고리즘 지식이 필요한 게 아니라 단순히 매트릭스에 대한 발상과 그걸 구현할 능력이 있는지 확인하는 문제인 것 같았다.

 

당구공은 필수적으로 한번 튕겨야 하는데 이 경우의 수는 총 4가지이므로 이를 각각 구현하였다. 상, 하, 좌, 우로 튕길 때 검은공(타겟 위치)가 흰공(시작 위치)의 진행경로 상에 존재하면 안 된다.

 

 

첫 번째 케이스의 조건문을 예로 들면 체크해야 할 부분은 두 점의 행이 같으면서 시작점이 끝점보다 왼쪽인 경우를 동시에 만족하는 경우이다. 이 경우 우측으로 이동하면서 검은 공을 치기 때문에 불가능하다.

구현 시 반대 케이스들에 대한 or 연산을 수행해서 위의 경우의 수를 제외할 수 있다.

if start[0]!=end[0] or start[1] > end[1]:

 

나머지는 그냥 x, y좌표의 거리차를 제곱하여 거리를 구하고 가장 작은 거리를 고르면 된다.

 

추가적으로 우 혹은 하 방향으로 이동할 때 시작점과 끝점의 거리를 빼는 것이 아닌 벽의 크기에서 각 값을 빼준다.

이는 팅기는 방향이 x, y좌표만큼이 아닌 벽에서 x혹은 y값을 뺀 만큼 진행하기 때문이다.