C++로 좌표점들이 직선을 이루는지 확인하는 방법

문제 개요

(x, y) 좌표로 구성된 데이터 포인트 목록이 주어졌을 때, 이 점들이 하나의 직선 위에 있는지 확인해야 합니다. 예를 들어, 점들이 [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]과 같이 주어진다면, 모든 점이 동일한 기울기를 가지므로 하나의 직선을 형성합니다.

접근 방법

이 문제를 해결하는 핵심 아이디어는 기울기(slope)를 활용하는 것입니다.

모든 인접한 두 점 사이의 기울기가 동일하다면, 그 점들은 반드시 같은 직선 위에 있습니다. 따라서 다음 단계로 진행합니다:

1. 첫 번째 두 점 사이의 기울기를 기준값으로 계산합니다.
2. 나머지 모든 연속된 점 쌍에 대해 기울기를 구합니다.
3. 모든 기울기가 기준값과 같으면 true를 반환하고, 하나라도 다르면 false를 반환합니다.

기울기 비교 시 주의점

부동소수점 나눗셈은 오차를 유발할 수 있으므로, 기울기를 직접 나누어 비교하는 대신 최대공약수(GCD)를 이용해 dx와 dy를 약분한 후 정수 형태로 비교하는 것이 안전합니다. 또한 x좌표가 모두 같거나 y좌표가 모두 같은 수직·수평선 경우도 자연스럽게 처리됩니다.

C++ 구현 예제

다음 코드를 통해 더 잘 이해할 수 있습니다:

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int gcd(int a, int b){
        return !b?a:gcd(b,a%b);
    }
    bool checkStraightLine(vector<vector<int>>& c) {
        bool ans = true;
        int a = c[1][0]-c[0][0];
        int b = c[1][1]-c[0][1];
        int cc = gcd(a,b);
        a/=cc;
        b/=cc;
        for(int i = 1; i < c.size(); i++){
            int x = c[i][0]-c[i-1][0];
            int y = c[i][1]-c[i-1][1];
            int z = gcd(x,y);
            x/=z;
            y/=z;
            ans = ans &&(x == a) && (y == b);
        }
        return ans;
    }
};
main(){
Solution ob;
vector<vector<int>> c = {{1,2},{2,3},{3,4},{4,5},{5,6},{6,7}};
cout << ob.checkStraightLine(c);
}

입력

[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

출력

1
(1은 true를 의미)

동작 원리 설명

위 코드에서는 먼저 첫 두 점의 좌표 차이(dx, dy)를 구하고, GCD로 약분하여 기준 방향 벡터를 만듭니다. 이후 각 인접 점 쌍에 대해서도 같은 방식으로 약분한 벡터를 구해 기준 벡터와 일치하는지 확인합니다. 모든 벡터가 일치하면 해당 점들은 직선 위에 있다는 뜻입니다.

시간 복잡도

n개의 점이 있을 때 각 점 쌍마다 GCD 계산을 수행하므로, 전체 시간 복잡도는 O(n log M)입니다(M은 좌표 값의 최대 크기). 공간 복잡도는 O(1)로 추가 메모리가 거의 필요하지 않습니다.