파이썬(Python)으로 한 점을 다른 점으로 변환할 수 있는지 확인하는 프로그램

시작점 (sx, sy)와 목표점 (tx, ty)가 주어졌을 때, 시작점에서 목표점까지 도달하는 일련의 이동이 존재하는지 확인해야 합니다. 여기서 각 이동은 점 (x, y)를 (x, x+y) 또는 (x+y, y)로 변형하는 것을 의미합니다.

예를 들어 입력이 (sx, sy) = (1,1), (tx, ty) = (4,5)라면 출력은 True가 됩니다. 그 이유는 (1,1) → (2,1) → (3,1) → (4,1) → (4,5) 순서로 이동할 수 있기 때문입니다.

문제 해결 접근 방식

이 문제는 재귀적으로 해결할 수 있으며, 다음 단계를 따릅니다.

• solve() 함수를 정의합니다. 이 함수는 sx, sy, tx, ty 네 개의 매개변수를 받습니다.
• sx > tx 또는 sy > ty인 경우, 시작점이 이미 목표점 범위를 벗어났으므로 False를 반환합니다.
• sx == tx인 경우, y 좌표만 남은 차이만큼 증가할 수 있는지 확인하기 위해 (ty - sy) mod sx == 0 인지를 반환합니다.
• sy == ty인 경우, 마찬가지로 (tx - sx) mod sy == 0 인지를 반환합니다.
• 그 외의 경우에는 역방향으로 거슬러 올라가며 solve(sx, sy, tx-ty, ty) 또는 solve(sx, sy, tx, ty-tx)를 재귀 호출하여 결과를 반환합니다.

핵심 아이디어는 정방향 탐색 대신 목표점에서 시작점으로 거꾸로 추적하면 경우의 수를 크게 줄일 수 있다는 점입니다. 두 좌표 중 더 큰 값에서 작은 값을 빼는 연산을 반복하면, 모듈로 연산을 활용해 효율적으로 판단할 수 있습니다.

예제 구현

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(sx, sy, tx, ty):
    if sx > tx or sy > ty:
        return False
    if sx == tx:
        return (ty - sy) % sx == 0
    if sy == ty:
        return (tx - sx) % sy == 0
    return solve(sx, sy, tx - ty, ty) or solve(sx, sy, tx, ty - tx)

(sx, sy) = (1, 1)
(tx, ty) = (4, 5)
print(solve(sx, sy, tx, ty))

입력

(1,1), (4,5)

출력

True