C++로 선분이 지나가는 단위 정사각형의 개수 구하기

문제 개요

격자 평면 위에서 두 끝점 (x1, y1)과 (x2, y2)가 주어졌을 때, 이 두 점을 잇는 선분이 통과하는 단위 면적(1×1) 정사각형의 개수를 구하는 것이 목표입니다.

핵심 아이디어와 공식

선분이 지나가는 정사각형의 개수를 구하려면 다음 세 가지 값을 계산해야 합니다.

x 좌표의 차 (dx) = x2 − x1
y 좌표의 차 (dy) = y2 − y1
결과값 = dx + dy − gcd(dx, dy)

여기서 최대공약수(gcd)를 빼는 이유는, 선분이 세로 격자선과 가로 격자선을 동시에 통과하는 지점에서는 새로운 정사각형이 하나만 추가되기 때문입니다. 즉, dx + dy에서 중복으로 세어진 횟수인 gcd(dx, dy)만큼 차감해 주는 것입니다.

알고리즘 동작 방식

unitSquares(int x1, int y1, int x2, int y2) 함수는 네 개의 좌표 값 x1, y1, x2, y2를 입력받습니다. 먼저 x2와 x1의 절댓값 차이(dx), 그리고 y2와 y1의 절댓값 차이(dy)를 각각 계산합니다. 그다음 dx와 dy를 더한 값에서 두 수의 최대공약수를 뺀 결과를 ans 변수에 저장하고, 이를 main 함수로 반환하여 출력합니다.

int unitSquares(int x1, int y1, int x2, int y2){
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int ans = dx + dy - __gcd(dx, dy);
    return ans;
}

전체 구현 예제

다음은 선분이 통과하는 단위 면적 정사각형의 개수를 구하는 전체 코드입니다.

#include<iostream>
#include <algorithm>
using namespace std;

int unitSquares(int x1, int y1, int x2, int y2){
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int ans = dx + dy - __gcd(dx, dy);
    return ans;
}

int main(){
    int x1 = 3, y1 = 3, x2 = 12, y2 = 6;
    cout<<"The line passes through "<<unitSquares(x1, y1, x2, y2)<<" squares ";
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

The line passes through 9 squares

예제에서 dx = |12 − 3| = 9, dy = |6 − 3| = 3이며, gcd(9, 3) = 3이므로 결과는 9 + 3 − 3 = 9개가 됩니다. 이 알고리즘의 시간 복잡도는 유클리드 호제법에 기반한 gcd 연산이 지배하므로 O(log(min(dx, dy)))로 매우 효율적입니다.