C++ 코딩테스트 강좌, 선분의 교차 여부 구하기

안녕하세요, 코딩테스트를 준비하는 여러분! 이번 강좌에서는 C++를 활용하여 선분의 교차 여부를 구하는 문제를 다루어 보겠습니다. 이 문제는 기하학적 알고리즘 문제 중 하나로, 여러 가지 응용이 가능하기 때문에 코딩테스트에서 자주 출제됩니다.

문제 설명

주어진 두 개의 선분이 교차하는지 판단하는 문제입니다. 선분 A는 두 점 P1(x1, y1)와 P2(x2, y2)로 이루어져 있고, 선분 B는 두 점 P3(x3, y3)와 P4(x4, y4)로 이루어져 있다고 가정합시다. 우리의 목표는 선분 A와 선분 B가 교차하는지 여부를 결정하는 것입니다.

문제의 입력

첫 번째 선분의 끝점 P1과 P2의 좌표 (x1, y1), (x2, y2)
두 번째 선분의 끝점 P3와 P4의 좌표 (x3, y3), (x4, y4)

문제의 출력

선분 A와 선분 B가 교차하는 경우 “1”을, 그렇지 않을 경우 “0”을 출력합니다.

문제 접근 방법

선분의 교차 여부를 판단하기 위해서 우리는 주어진 두 선분이 서로 교차하는지를 쉽게 판단할 수 있는 기하학적 방법을 사용할 것입니다. 여기서 고려해야 할 몇 가지 경우가 있습니다:

두 선분이 평행하는 경우
한 선분이 다른 선분을 가로막는 경우
두 선분의 끝점이 동일한 경우
특정 조건에서의 접촉 여부

기하학적 개념

선분의 교차 여부를 판별하기 위해, 우리는 벡터를 사용한 기하학적 접근을 할 것입니다. 두 선분의 방정식을 표기할 수 있으며, 이들을 벡터로 변환 후 교차 여부를 판단할 수 있습니다.

두 점 (x1, y1)과 (x2, y2)에서 선분 A를 생각하고, 두 점 (x3, y3)과 (x4, y4)에서 선분 B를 생각해 봅시다. 선분 A와 B가 교차하는지는 선분의 끝점과 벡터의 위치 관계를 통해 쉽게 파악할 수 있습니다.

위치 관계

선분 A의 두 점을 연결하는 벡터 AB와 선분 B의 두 점을 연결하는 벡터 CD의 방향을 파악해야 합니다. 일반적으로 이 선분들이 서로 교차할 경우, 각 점은 서로 다른 방향에 위치하게 됩니다.

벡터의 크로스 프로덕트

벡터의 크로스 프로덕트를 이용하여 두 벡터의 방향을 비교할 수 있습니다. 두 벡터, 즉 선분의 두 방향을 나타내는 벡터를 AB와 AC라 할 때, 이들의 크로스 프로덕트를 계산함으로써 두 선분의 위치 관계를 알 수 있습니다.

수학적 표현

수학적으로 벡터의 크로스 프로덕트는 다음과 같이 표현됩니다:

    AB x AC = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)

이와 같은 방식으로, 각각의 점에 대해 크로스 프로덕트를 계산하여, 각 선분의 방향을 결정할 수 있습니다. 만약 양수, 음수, 또는 0으로 나오는 경우에 따라 서로 교차하거나 혹은 평행하게 위치하게 되는 상황을 나누어 확인할 수 있습니다.

C++ 코드 구현

이제 위에서 설명한 이론을 바탕으로 C++ 코드를 작성해 보겠습니다. 이 코드에서는 선분의 위치 관계를 파악하고 교차 여부를 체크하는 로직을 포함할 것입니다.


#include 

using namespace std;

struct Point {
    int x, y;
};

// 두 선분이 교차하는지 여부를 체크하는 함수
bool doIntersect(Point p1, Point p2, Point p3, Point p4) {
    // 오리엔테이션 계산
    auto orientation = [](Point a, Point b, Point c) {
        int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
        if (val == 0) return 0; // collinear
        return (val > 0) ? 1 : 2; // clock or counterclock wise
    };

    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // 일반적인 경우
    if (o1 != o2 && o3 != o4)
        return true;

    // 특별한 경우
    // ...
    return false;
}

int main() {
    Point p1 = {1, 1}, p2 = {10, 1}, p3 = {1, 2}, p4 = {10, 2};
    if (doIntersect(p1, p2, p3, p4)) {
        cout << "선분이 교차합니다." << endl;
    } else {
        cout << "선분이 교차하지 않습니다." << endl;
    }
    return 0;
}

코드 분석

위 코드에서 우리는 먼저 두 점을 구조체(Point)로 정의하고, 선분의 교차 여부를 확인하기 위한 doIntersect 함수를 작성했습니다. 이 함수는 주어진 네 점에 대한 오리엔테이션을 계산하고, 이를 통해 선분이 교차하는지 여부를 판단합니다. 각 오리엔테이션의 조합을 통해 서로 다른 교차 조건을 확인하고, 마지막에 결과를 반환합니다.

테스트 케이스

위 코드를 테스트하기 위해 다양한 테스트 케이스를 사용할 수 있습니다. 몇 가지 예를 들어 보겠습니다:


    // 교차 케이스
    Point p1 = {0, 0}, p2 = {10, 10}, p3 = {0, 10}, p4 = {10, 0};
    // 교차하지 않는 경우
    Point p1 = {1, 1}, p2 = {10, 1}, p3 = {1, 2}, p4 = {10, 2};

결론

이번 강좌에서는 C++를 이용하여 선분의 교차 여부를 확인하는 알고리즘을 구현하는 과정을 살펴보았습니다. 기하학적 문제는 코딩테스트에서 자주 요구되는 주제 중 하나이므로, 기초적인 기하학 개념을 숙지하는 것이 중요합니다. 다양한 예제와 연습문제를 통해 알고리즘을 더욱 깊이 이해할 수 있을 것입니다.

추가 연습 문제

아래의 문제를 풀어보며 연습해보세요:

교차하는 경우와 교차하지 않는 경우를 포함한 여러 테스트 케이스 작성하기
선분이 접하는 경우를 고려하여 코드를 확장하기
3차원 공간에서의 선분 교차 여부 구하기

이상으로 C++ 코딩 테스트 강좌를 마치겠습니다. 앞으로도 다양한 알고리즘 문제를 다루어 보겠습니다. 감사합니다!