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

프로그래밍 대회나 코딩 테스트에서 선분의 교차 여부를 판단하는 문제는 자주 출제되는 주제 중 하나입니다. 이 강좌에서는 Kotlin 언어를 사용하여 선분의 교차 여부를 구하는 방법을 알아보겠습니다. 이 과정을 통해 기하학적 기법과 수학적 사고를 기를 수 있습니다. 또한, 다양한 테스트 케이스를 통해 알고리즘의 정확성을 검증할 것입니다.

문제 설명

두 선분이 주어졌을 때, 이 두 선분이 서로 교차하는지 여부를 판단하는 문제입니다. 선분 A는 점 P1(x1, y1)과 점 P2(x2, y2)로 정의되고, 선분 B는 점 Q1(x3, y3)과 점 Q2(x4, y4)로 정의됩니다. 교차할 경우 “YES”를, 교차하지 않을 경우 “NO”를 출력하여야 합니다.

입력 형식

  • 첫 번째 줄에 선분 A의 두 점 P1, P2를 나타내는 정수 x1, y1, x2, y2가 공백으로 구분되어 주어진다.
  • 두 번째 줄에 선분 B의 두 점 Q1, Q2를 나타내는 정수 x3, y3, x4, y4가 공백으로 구분되어 주어진다.

출력 형식

교차 여부에 따라 “YES” 또는 “NO”를 출력한다.

문제 접근 방법

선분 교차 여부를 판단하기 위해 다음과 같은 절차를 따릅니다:

  1. 두 선분이 교차하기 위해서는 서로의 방향성을 고려해야 합니다.
  2. 두 선분의 각각의 끝 점과 다른 선분의 두 점을 사용하여 방향을 판단합니다.
  3. 선분의 교차 여부는 구간과 위치를 통해 판단할 수 있습니다.

구체적으로는 선분 A의 점 P1과 P2가 선분 B의 점 Q1과 Q2를 통해 반시계 방향인지 시계 방향인지 판단할 수 있습니다. 이를 통해 교차 여부를 판별할 수 있습니다.

Kotlin 코드 구현

이제 Kotlin 언어로 구현된 코드를 살펴보겠습니다. 아래 코드는 선분 A와 B의 교차 여부를 판단하는 간단한 예시입니다.


fun main() {
    val (x1, y1, x2, y2) = readLine()!!.split(" ").map { it.toInt() }
    val (x3, y3, x4, y4) = readLine()!!.split(" ").map { it.toInt() }

    if (doIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) {
        println("YES")
    } else {
        println("NO")
    }
}

// 두 점의 방향성을 계산
fun orientation(px: Int, py: Int, qx: Int, qy: Int, rx: Int, ry: Int): Int {
    val value = (qy - py) * (rx - qx) - (qx - px) * (ry - qy)
    return when {
        value == 0 -> 0 // 직선
        value > 0 -> 1  // 반시계 방향
        else -> 2       // 시계 방향
    }
}

// 두 선분이 교차하는지 판단하는 함수
fun doIntersect(x1: Int, y1: Int, x2: Int, y2: Int, x3: Int, y3: Int, x4: Int, y4: Int): Boolean {
    val o1 = orientation(x1, y1, x2, y2, x3, y3)
    val o2 = orientation(x1, y1, x2, y2, x4, y4)
    val o3 = orientation(x3, y3, x4, y4, x1, y1)
    val o4 = orientation(x3, y3, x4, y4, x2, y2)

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

    // 선분이 같은 선 위에 있을 때의 예외 처리
    if (o1 == 0 && onSegment(x1, y1, x3, y3, x2, y2)) return true
    if (o2 == 0 && onSegment(x1, y1, x4, y4, x2, y2)) return true
    if (o3 == 0 && onSegment(x3, y3, x1, y1, x4, y4)) return true
    if (o4 == 0 && onSegment(x3, y3, x2, y2, x4, y4)) return true

    return false
}

// 주어진 점이 선분 위에 있는지 판단하는 함수
fun onSegment(px: Int, py: Int, qx: Int, qy: Int, rx: Int, ry: Int): Boolean {
    return (rx <= maxOf(px, qx) && rx >= minOf(px, qx) &&
            ry <= maxOf(py, qy) && ry >= minOf(py, qy))
}

코드 설명

위의 코드는 선분 A와 B의 교차 여부를 판단하는 과정을 구현한 것입니다.

  • orientation 함수: 이 함수는 주어진 세 점 (P, Q, R)의 방향을 계산합니다. 방향에 따라 값이 0 (직선), 1 (반시계 방향), 2 (시계 방향)로 분류됩니다. 이 값은 교차 여부를 판단하는 데 사용됩니다.
  • doIntersect 함수: 이 함수는 각 선분의 방향성을 계산하고, 일반적인 경우와 예외적인 경우를 판단하여 결과를 반환합니다.
  • onSegment 함수: 주어진 점 R이 선분 PQ 위에 있는지를 판단합니다. 선분의 양 끝 점과 비교하여 R의 위치가 선분 내에 포함되는지를 체크합니다.

테스트 케이스

이제 다양한 테스트 케이스를 통해 코드의 정확성을 확인하겠습니다.

  • 테스트 케이스 1: 0 0 2 2 0 2 2 0 → 결과: YES
  • 테스트 케이스 2: 1 1 10 1 1 2 10 2 → 결과: NO
  • 테스트 케이스 3: 10 0 0 10 0 0 10 10 → 결과: YES
  • 테스트 케이스 4: 1 1 3 3 1 3 3 1 → 결과: YES
  • 테스트 케이스 5: 0 0 0 10 0 5 10 5 → 결과: NO

결론

이번 강좌에서는 선분의 교차 여부를 판단하는 효율적인 알고리즘을 Kotlin으로 구현하였습니다. 기하학적인 개념을 기반으로 한 이 문제는 다양한 상황에서 유용하게 활용될 수 있습니다. 적용 가능한 다양한 알고리즘과 기법을 통해 다양한 문제를 풀어보는 경험이 중요합니다.

코드와 테스트 케이스를 실제로 구현하고 실행해보며 알고리즘의 동작 방식을 명확하게 이해하는 것이 중요합니다. 지속적으로 실습하면 기하학적 문제 해결 능력을 키울 수 있습니다.