Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 수직 구간 내 직선 교차점 찾는 방법 (정렬 기반 풀이)

문제 소개

y = mx + c 형태의 직선이 여러 개 주어져 있다고 가정해 봅시다. 이 직선들과 수직 구간(세로 경계)이 이루는 영역 안에서, 주어진 구간에 서로 다른 직선의 교차점이 존재하는지 판별하는 것이 목표입니다.

예를 들어 다음과 같은 네 개의 직선이 있다고 합시다.

  • L1 = y = x + 2
  • L2 = y = −x + 7
  • L3 = y = −3
  • L4 = y = 2x − 7

그리고 수직 구간은 x = 2부터 x = 4까지로 주어집니다. 이 예제에서는 L1과 L2의 교차점이 해당 구간 안에 포함되므로 정답은 true가 됩니다.

풀이 아이디어: 정렬 활용

이 문제는 정렬 기법을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.

  1. 경계와의 교차점 계산: 각 직선이 수직 구간의 양쪽 경계(x = 왼쪽 경계, x = 오른쪽 경계)와 만나는 점을 구합니다.
  2. y좌표만 저장: 교차점의 x좌표는 경계값 자체와 동일하므로, y좌표 값만 (왼쪽 경계 y값, 오른쪽 경계 y값) 형태의 pair로 저장하면 충분합니다.
  3. 정렬: 왼쪽 경계에서의 y값을 기준으로 모든 pair를 오름차순으로 정렬합니다.
  4. 순서 뒤집힘 검사: 정렬된 pair를 차례대로 순회하면서, 현재 pair의 두 번째 값(오른쪽 경계 y값)이 바로 앞 pair의 두 번째 값보다 작은 경우가 하나라도 있으면 구간 내에 교차점이 존재합니다.

왜 이 방법이 성립할까요? 두 직선이 구간 내에서 만나지 않는다면, 왼쪽 경계에서의 위·아래 순서가 오른쪽 경계에서도 그대로 유지됩니다. 따라서 정렬 후 오른쪽 경계 y값의 순서가 뒤바려 있다면, 그 사이 어딘가에서 두 직선이 반드시 교차했다는 의미입니다.

C++ 구현 예제

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

class Line {
public:
    int slope, intercept;
    Line() {}
    Line(int slope, int intercept) : slope(slope), intercept(intercept) {}
};

// 직선 l 위에서 x좌표에 대응하는 y값 반환
int getYCoordinate(const Line& l, int x) {
    return l.slope * x + l.intercept;
}

// [leftRange, rightRange] 구간 안에 교차점이 있는지 확인
bool hasIntersectionPoint(vector<Line>& lines, int leftRange, int rightRange) {
    vector<pair<int, int>> yBorder(lines.size());

    // 양쪽 경계에서의 y좌표를 pair로 저장
    for (size_t i = 0; i < lines.size(); i++) {
        yBorder[i] = make_pair(
            getYCoordinate(lines[i], leftRange),
            getYCoordinate(lines[i], rightRange)
        );
    }

    // 왼쪽 경계 y값(first)을 기준으로 정렬
    sort(yBorder.begin(), yBorder.end());

    // 오른쪽 경계 y값(second)의 순서가 뒤바졌는지 검사
    for (size_t i = 1; i < yBorder.size(); i++) {
        if (yBorder[i].second < yBorder[i - 1].second)
            return true;
    }
    return false;
}

int main() {
    vector<Line> lines = {
        Line(1, 2),   // y = x + 2
        Line(-1, 7),  // y = -x + 7
        Line(0, -3),  // y = -3
        Line(2, -7)   // y = 2x - 7
    };

    int leftRange = 2;
    int rightRange = 4;

    if (hasIntersectionPoint(lines, leftRange, rightRange)) {
        cout << "교차점이 " << leftRange << " 와 " << rightRange << " 사이에 존재합니다";
    } else {
        cout << leftRange << " 와 " << rightRange << " 사이에는 교차점이 없습니다";
    }
    return 0;
}

실행 결과

교차점이 2 와 4 사이에 존재합니다

복잡도 분석

  • 시간 복잡도: O(N log N) — 각 직선과 경계의 교차점 계산에 O(N), 정렬에 O(N log N)이 소요됩니다.
  • 공간 복잡도: O(N) — 경계에서의 교차점 y값을 저장하기 위한 pair 배열이 필요합니다.

마무리

이처럼 직선들을 경계에서의 y값 순서대로 정렬한 뒤 순서 역전 여부만 확인하면, 실제 교차점 좌표를 일일이 계산하지 않고도 구간 내 교차 여부를 빠르게 판별할 수 있습니다. "두 대상의 상대적 순서가 유지되는가?"라는 관찰은 기하 알고리즘에서 매우 유용하게 쓰이는 패턴이므로 기억해 두면 좋습니다.