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

안녕하세요! 이번 포스트에서는 C#을 이용한 코딩 테스트 문제 중 ‘선분의 교차 여부 구하기’에 대해 다루어 보겠습니다.
이 문제는 기하학적인 문제로, 주어진 두 선분이 서로 교차하는지를 판단하는 것입니다. 여러 분야에서 활용되는 기초적인 문제이기 때문에,
알고리즘 문제 풀이 능력과 수학적 사고력을 향상시키는 데 유용합니다.

문제 설명

두 점 A(x1, y1)와 B(x2, y2)를 가지는 선분 1과 두 점 C(x3, y3)와 D(x4, y4)를 가지는 선분 2가 주어졌을 때,
두 선분이 교차하는지 여부를 판단하는 프로그램을 작성하세요.

입력

• 첫 번째 선분의 두 점 A, B의 좌표: (x1, y1), (x2, y2)
• 두 번째 선분의 두 점 C, D의 좌표: (x3, y3), (x4, y4)

출력

두 선분이 교차하면 true, 그렇지 않으면 false를 출력하세요.

문제 해결 접근 방식

이 문제를 해결하기 위해서는 선분의 위치 관계를 파악할 필요가 있습니다. 선분이 교차하기 위해서는 다음 두 가지 조건을 모두 만족해야 합니다:

1. 선분 AB의 끝점이 선분 CD의 서로 다른 방향에 위치해야 합니다.
2. 선분 CD의 끝점이 선분 AB의 서로 다른 방향에 위치해야 합니다.

수학적 배경

각 점이 주어졌을 때, 벡터의 외적을 이용하여 두 점이 서로 다른 쪽에 위치하는지를 판단할 수 있습니다.
두 벡터 v1 = B - A와 v2 = C - A의 외적의 부호가 다르다면 점 C가 선분 AB의 한쪽에,
점 D가 반대쪽에 위치한 것이 됩니다. 이와 같은 방법으로 선분의 교차 여부를 판단할 수 있습니다.

구현 방법

문제를 해결하기 위한 기본 로직은 다음과 같습니다:

1. 주어진 4개의 점 A, B, C, D를 사용하여 각 선분의 방향을 정의한다.
2. 외적 함수를 만들어 두 벡터의 외적을 계산한다.
3. 두 점의 경우에 따라 외적의 부호를 비교하고 교차 여부를 반환한다.

C# 코드 구현

using System;

class Program
{
    static void Main()
    {
        // 점 A, B, C, D의 좌표 입력
        int[] A = { 1, 1 }; // (x1, y1)
        int[] B = { 4, 4 }; // (x2, y2)
        int[] C = { 1, 4 }; // (x3, y3)
        int[] D = { 4, 1 }; // (x4, y4)

        // 교차 여부 확인
        bool isCross = DoSegmentsIntersect(A, B, C, D);
        Console.WriteLine(isCross ? "true" : "false");
    }

    static bool DoSegmentsIntersect(int[] A, int[] B, int[] C, int[] D)
    {
        // 외적을 이용한 선분 교차 확인
        int d1 = CrossProduct(A, B, C);
        int d2 = CrossProduct(A, B, D);
        int d3 = CrossProduct(C, D, A);
        int d4 = CrossProduct(C, D, B);

        // 서로 다른 방향에 위치해야 교차
        if (d1 * d2 < 0 && d3 * d4 < 0)
            return true;

        // 선분이 끝점에 겹치는 경우도 고려
        if (d1 == 0 && IsOnSegment(A, B, C)) return true;
        if (d2 == 0 && IsOnSegment(A, B, D)) return true;
        if (d3 == 0 && IsOnSegment(C, D, A)) return true;
        if (d4 == 0 && IsOnSegment(C, D, B)) return true;

        return false;
    }

    static int CrossProduct(int[] A, int[] B, int[] C)
    {
        // 벡터 외적 계산
        return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]);
    }

    static bool IsOnSegment(int[] A, int[] B, int[] P)
    {
        // 점 P가 선분 AB 위에 있는지 확인
        return Math.Min(A[0], B[0]) <= P[0] && P[0] <= Math.Max(A[0], B[0]) &&
               Math.Min(A[1], B[1]) <= P[1] && P[1] <= Math.Max(A[1], B[1]);
    }
}

코드 설명

위의 코드를 통해 선분 교차 문제를 해결할 수 있습니다. 각 함수의 세부 설명은 다음과 같습니다.

• Main: 프로그램의 진입점으로, 각 선분의 점을 설정하고 교차 여부를 확인하는 역할을 합니다.
• DoSegmentsIntersect: 두 선분의 교차 여부를 판단하는 핵심 로직을 구현한 함수입니다.
• CrossProduct: 주어진 세 점을 이용하여 외적을 계산합니다. 외적의 결과를 통해 방향을 판단합니다.
• IsOnSegment: 특정 점이 선분 위에 위치하는지 판단하는 함수입니다.

테스트 케이스

주어진 코드를 테스트하기 위해 몇 가지 테스트 케이스를 고려할 수 있습니다.

결론

이번 글에서는 C#을 사용하여 선분의 교차 여부를 판단하는 알고리즘을 구현해 보았습니다.
기하학적 문제는 이러한 문제 해결 방식을 이해하는 데 도움이 되며, 고급 알고리즘을 배우는 기초가 되기도 합니다.
앞으로도 다양한 알고리즘 문제를 함께 풀어보시기 바랍니다. 감사합니다!