파이썬으로 두 점을 잇는 직선 위의 정수 좌표 개수 구하기

두 개의 점 (p1, q1)과 (p2, q2)가 주어졌다고 가정해 봅시다. 이 두 점을 지나는 직선을 그렸을 때, 그 직선 위에 존재하는 정수 좌표(x 값과 y 값이 모두 정수인 점)의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 p1 = 3, q1 = 3, p2 = 6, q2 = 6이라면 출력은 2가 됩니다. 두 점을 잇는 직선을 그려 보면 (5, 5)와 (6, 6)이라는 점이 직선 위에 위치하는 것을 확인할 수 있습니다.

문제 해결 접근 방법

이 문제는 최대공약수(GCD)를 활용하면 아주 간단하게 해결할 수 있습니다. 두 점의 x 좌표 차이를 dx = |p2 − p1|, y 좌표 차이를 dy = |q2 − q1|라고 할 때, 선분 위의 정수 좌표 개수는 gcd(dx, dy) − 1과 같습니다.

그 이유는 두 점을 잇는 선분이 항상 gcd(dx, dy)개의 동일한 길이의 구간으로 나누어지며, 그 경계에 해당하는 내부 분점들이 바로 정수 좌표가 되기 때문입니다. 양 끝점 두 개는 제외해야 하므로 마지막에 1을 빼주는 것입니다.

알고리즘 단계

• gcd_find() 함수를 정의합니다. 이 함수는 x, y 두 값을 인자로 받습니다.
  • y가 0이면 x를 그대로 반환합니다.
  • 그렇지 않으면 gcd_find(y, x mod y)를 재귀적으로 호출한 결과를 반환합니다. (유클리드 호제법)

메인 함수에서는 다음과 같이 처리합니다.

• gcd_find(|p2 − p1|, |q2 − q1|) − 1을 반환합니다.

예제 코드

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

def gcd_find(x,y):
   if y == 0:
      return x
   return gcd_find(y,x % y)

def solve(p1,q1,p2,q2):
   return gcd_find(abs(p2 - p1),abs(q2 - q1)) - 1

print(solve(3,3,6,6))

입력

3,3,6,6

출력

2

시간 복잡도

유클리드 호제법을 이용한 최대공약수 계산은 O(log(min(dx, dy)))의 시간 복잡도를 가지므로, 좌표 값이 매우 큰 경우에도 효율적으로 동작합니다.