[Kotlin, S3] 백준 1004번 어린 왕자

출처: unsplash.com

 

어린 왕자(1004번)

Silver 3

#수학 #기하학

 

문제 내용

 

 

문제 접근

시작 좌표와 끝 좌표가 주어지고, 행성계의 중심 좌표와 행성계의 반지름이 주어질 때, 시작 좌표에서 끝 좌표로 이동하면서 진입 또는 이탈하는 행성계의 개수를 구해야 한다.

행성계는 반지름과 중심 좌표가 주어진다. 시작 좌표와 행성계의 중심좌표 간의 거리와 끝 좌표와 행성계의 중심 좌표 간의 거리를 이용해 해당 행성계를 무조건 지나야 하는지 아니면 안 지나가도 상관없는지 알 수 있다.

 

 

시작 좌표와 행성계의 중심 좌표 간의 거리를 distanceStart, 끝 좌표와 행성계의 중심 좌표 간의 거리를 distanceEnd라고 할 때

행성계와 시작, 끝 좌표 간의 관계가 3가지가 나올 것이다.

 

<상황 1>

distanceStart와 distanceEnd가 행성계의 반지름보다 크다면 아래와 같이 형태가 나올 것이다.

사진 1-1

distanceEnd, distanceStart가 행성계의 반지름인 r보다 길기 때문에 충분히 행성계의 진입을 피할 수 있다.

 

<상황 2>

distanceStart 또는 distanceEnd가 행성계의 반지름보다 작다면 아래와 같은 형태가 나올 수 있다.

사진 1-2, ds: distanceStart, de: distanceEnd

위 사진에서는 distanceStart가 행성계의 반지름보다 작은 경우를 나타낸 것이다. start의 좌표가 행성계 내부에 존재하게 된다.

start에서 end로 이동하기 위해서는 무조건 행성계를 이탈해야 한다.

 

 

<상황 3>

distanceStart와 distanceEnd가 모두 행성계의 반지름보다 작은 경우에는 아래와 같은 형태가 나온다.

사진 1-3

distanceStart, distanceEnd가 모두 행성계의 반지름보다 작다. 이 경우에는 시작 좌표와 끝 좌표가 모두 한 행성계 내부에 존재한다.

행성계 내부에 두 좌표가 있지만 start에서 end로 이동하기 위해 굳이 행성계를 빠져나와서 end로 향할 이유가 없다. 그래서 이 경우는 행성계 진입, 이탈 모두 아닌 경우이다.

 

두 점 사이의 거리 공식으로 distanceStart, distanceEnd를 구하고, distanceStart, distanceEnd와 행성계의 반지름 같은 대소 관계를 잘 비교해서 상황 2인 경우에만 행성계 진입/이탈 카운트를 늘려 주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()
    val resultSb = StringBuilder()

    for (i in 0 until case) {
        val (startX, startY, endX, endY) = readLine().split(" ").map { it.toInt() }
        val planetCnt = readLine().toInt()
        var entryAndExit = 0

        for (j in 0 until planetCnt) {
            val (centerX, centerY, radius) = readLine().split(" ").map { it.toInt() }

            val distanceStartX = abs(startX - centerX).toDouble()
            val distanceStartY = abs(startY - centerY).toDouble()
            val distanceStart = sqrt(distanceStartX.pow(2) + distanceStartY.pow(2))

            val distanceEndX = abs(endX - centerX).toDouble()
            val distanceEndY = abs(endY - centerY).toDouble()
            val distanceEnd = sqrt(distanceEndX.pow(2) + distanceEndY.pow(2))

            if (distanceStart <= radius && distanceEnd <= radius) {
                continue
            } else if (distanceStart <= radius || distanceEnd <= radius) {
                entryAndExit++
            }
        }

        resultSb.append("$entryAndExit\n")
    }

    println(resultSb)
}

 

문제 풀이

시작 좌표를 startX, startY로 받고 끝 좌표를 endX, endY로 받아준다.

행성계의 중심좌표는 centerX, centerY로 받아주고, 반지름은 radius로 받는다.

start 좌표와 center 좌표 간의 거리를 distanceStart에 저장하고, end 좌표와 center 좌표 간의 거리를 distanceEnd로 저장한다.

 

이제 distanceStart와 distanceEnd가 모두 radius보다 작은 경우에는 상황 3에 해당한다. continue로 넘어간다.

distanceStart 또는 distanceEnd가 radius보다 작은 경우에는 상황 2에 해당한다. 행성계 진입/이탈 카운트를 늘린다.

 

 

문제 해결 과정

역시 문제 이해가 좀 어렵다.

사실 포스팅을 적기 전까지만 해도 문제 이해를 덜한 상태로 풀었는데, 직접 그려가면서 포스팅을 작성하다 보니 완벽하게 이해할 수 있었다.

두 점간의 거리와 행성계의 반지름의 길이 간의 대소 비교를 이용해 상황 유추 후 행성계 진입/이탈 횟수를 세줘야 한다.

 

그림이 꽤 복잡해서 처음 문제를 보게 되면 어리둥절할 수도 있다. 침작하게 문제를 읽으면서 문제를 이해해 보자.

결론은 이해하면 쉬운 문제.