[백준 1004] 어린 왕자

백준 1004번: 어린 왕자 - 상세 풀이

🔍 1. 문제 소개

어린 왕자는 사랑하는 장미를 구하기 위해 은하수를 여행합니다. 우주선이 행성계를 불필요하게 통과하는 것을 최소화해야 합니다. 출발점과 도착점, 그리고 여러 개의 행성계 정보(중심 좌표와 반지름)를 이용하여 어린 왕자가 반드시 통과해야 하는 행성계의 개수를 구하는 문제입니다.

💡 2. 문제 해석

출발점과 도착점 중 하나만 행성계 내부에 있을 때만 카운트합니다. 출발점과 도착점이 둘 다 행성 내부에 있거나 모두 외부에 있으면 카운트하지 않습니다. 행성 내부 여부는 피타고라스 정리를 이용한 거리 계산을 통해 판별합니다.

🧠 3. 접근 방법

• 각 행성계에 대해 출발점과 도착점이 내부에 있는지 확인
• 출발점과 도착점 중 하나만 내부에 있으면 카운트 증가
• 최종적으로 카운트 값을 출력

⚙️ 4. 구현 과정

1. 입력: 테스트 케이스 개수 T 입력
2. 반복: T번 반복하며 각 테스트 케이스 처리
3. 출발점 (x1, y1)과 도착점 (x2, y2) 입력
4. 행성계 개수 n 입력
5. 각 행성계 (cx, cy, r) 입력
6. 출발점과 도착점 중 하나만 내부에 있으면 카운트 증가
7. 출력: 최종 카운트 값

💻 5. 코드 설명

import kotlin.math.pow

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val (x1, y1, x2, y2) = readLine()!!.split(" ").map { it.toInt() }
        val n = readLine()!!.toInt()
        var count = 0
        repeat(n) {
            val (cx, cy, r) = readLine()!!.split(" ").map { it.toInt() }
            val dist1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy)
            val dist2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy)
            val rSquared = r * r

            if ((dist1 < rSquared && dist2 > rSquared) || (dist1 > rSquared && dist2 < rSquared)) {
                count++
            }
        }
        println(count)
    }
}

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

• 시간 복잡도: O(tn) (t는 테스트 케이스 개수, n은 행성계 개수)
• 공간 복잡도: O(1) (추가적인 공간 사용이 거의 없음)

🎯 7. 결론

이 문제는 간단한 기하학적 계산과 조건문을 활용하여 해결할 수 있습니다. 코드는 효율적이며, 시간과 공간 복잡도 모두 적절합니다. 실제 응용에서는 입력 최적화 및 예외 처리를 고려할 수 있지만, 이 문제의 경우 큰 영향을 미치지 않습니다.