C++로 두 점 사이의 정수 좌표점 개수 구하기

이 튜토리얼에서는 C++를 사용하여 주어진 두 점 사이에 존재하는 정수 좌표점(격자점)의 개수를 구하는 프로그램을 작성해 보겠습니다.

핵심 아이디어

두 점 사이의 정수점 개수는 다음 공식으로 간단하게 계산할 수 있습니다.

gcd(abs(x1 - x2), abs(y1 - y2)) - 1

여기서 gcd는 최대공약수(greatest common divisor)를 의미합니다. 다만, 두 점을 잇는 선분이 좌표축에 평행한 특수한 경우에는 아래와 같이 따로 처리해야 합니다.

• x축에 평행한 경우: 두 점의 y좌표가 같으므로 정수점 개수는 abs(x1 - x2) - 1
• y축에 평행한 경우: 두 점의 x좌표가 같으므로 정수점 개수는 abs(y1 - y2) - 1

예제

입력

pointOne = [1, 5]
pointTwo = [1, 3]

출력

1

두 점 모두 x좌표가 1로 동일하므로 선분은 y축에 평행합니다. 따라서 abs(5 - 3) - 1 = 1이 되어, 두 점 사이에 정수점이 하나 존재함을 알 수 있습니다.

알고리즘

• 두 점을 초기화합니다.
• 두 점의 x좌표가 같은지 확인합니다. 같다면 선분이 y축에 평행하므로 abs(y1 - y2) - 1을 반환합니다.
• 두 점의 y좌표가 같은지 확인합니다. 같다면 선분이 x축에 평행하므로 abs(x1 - x2) - 1을 반환합니다.
• 어느 축에도 평행하지 않다면 gcd(abs(x1 - x2), abs(y1 - y2)) - 1을 반환합니다.
• 결과를 계산하여 출력합니다.

구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int getCount(int pointOne[], int pointTwo[]) {
    if (pointOne[0] == pointTwo[0]) {
        return abs(pointOne[1] - pointTwo[1]) - 1;
    }
    if (pointOne[1] == pointTwo[1]) {
        return abs(pointOne[0] - pointTwo[0]) - 1;
    }
    return gcd(abs(pointOne[0] - pointTwo[0]), abs(pointOne[1] - pointTwo[1])) - 1;
}

int main() {
    int pointOne[] = {1, 3}, pointTwo[] = {10, 12};
    cout << getCount(pointOne, pointTwo) << endl;
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

8

이 예제에서 두 점은 (1, 3)과 (10, 12)입니다. gcd(abs(1 - 10), abs(3 - 12)) - 1 = gcd(9, 9) - 1 = 8이므로, 두 점 사이에는 정확히 8개의 정수점이 존재합니다.