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

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

난이도 : 실버 3
태그 : 수학, 기하학

 

 

설명

진입 / 이탈 횟수를 최소로 하는 경로를 찾아야 합니다.

각 행성계와 시작점, 도착점에 따라 나올 수 있는 경우의 수는 3가지 입니다.

 

1) 시작, 도착점 모두 행성계 외부에 있을 때

 

시작, 도착점 모두 행성계 외부에 있을 경우,

해당 행성계는 진입/ 이탈 할 필요가 없습니다.

 

2) 시작, 도착점 모두 행성계 안쪽에 있을 때

 

시작점, 도착점 모두 행성계 안에 있는 경우입니다.

이 경우 역시 위와 같이 진입 / 이탈 할 필요가 없습니다.

 

3) 시작점, 도착점 중 하나만 행성계 안에 있고, 다른 하나는 행성계 밖에 있을 때

마지막은 시작점, 도착점 중 하나만 행성계 안에 있고, 다른 한 점은 행성계 밖에 있는 경우입니다.

이 경우에만 행성계의 진입 / 이탈이 필요합니다.

 

접근방법

시작점, 도착점, 행성계의 위치와 행성계의 반지름에 따른 경우의 수를 구했으니,

이를 토대로 문제에 접근해봅시다.

1. 행성계 하나를 선택한다

2. 해당 행성계 안에 시작점, 도착점이 있는지 확인한다

( 시작점, 도착점이 행성계 안에 있는지 확인하기 위해선,

시작/도착점의 좌표와 행성계 중심의 좌표간의 거리(피타고라스 이용)가 반지름 r 보다 큰지, 작은지로 판단

3. 시작, 도착점 중 하나만 행성계 안에 있고, 다른 점은 바깥에 있다면 진입/이탈 횟수를 +1 한다

4. 아직 확인하지 않은 다른 행성계에 대해 1~3 과정을 수행한다.

 

 

소스코드

import java.util.StringTokenizer
import kotlin.math.pow
import kotlin.math.sqrt

data class Planet(val x: Int, val y: Int, val r: Int)

fun main() = with(System.`in`.bufferedReader()) {

    val sb = StringBuilder()

    repeat(readLine().toInt()) {
        // 진입 / 이탈 횟수 카운트
        var cnt = 0

        val (startX, startY, endX, endY) = readLine().split(" ").map { it.toInt() }

        val planetCnt = readLine().toInt()
        val planetArray = Array<Planet?>(planetCnt) { null }

        repeat(planetCnt) {
            val st = StringTokenizer(readLine())
            // 행성의 x, y, 반지름
            planetArray[it] = Planet(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt())
        }

        planetArray.forEach {
            val startDistance = getDistance(it!!.x, it.y, startX, startY)
            val endDistance = getDistance(it.x, it.y, endX, endY)

            // 행성이 두 점 모두 포함하거나, 두 점 모두 포함하지 않으면 진입 / 이탈 해야함
            if (!(startDistance > it.r && endDistance > it.r || startDistance < it.r && endDistance < it.r)) {
                cnt++
            }
        }

        sb.append("$cnt\n")
    }
    print(sb)
}

fun getDistance(x1: Int, y1: Int, x2: Int, y2: Int): Double {
    return sqrt((x1 - x2).toDouble().pow(2) + (y1 - y2).toDouble().pow(2))
}

 

좌표평면 위에서, 두 점간의 거리는 피타고라스를 사용해 구할 수 있습니다.

 

 

후기

기하학 문제는 많이 익숙하지 않아, 처음 봤을때 이게 뭐지...? 싶었는데,

문제를 천천히 다시 읽어보니,

그냥 두 점 중 하나만 행성계 안에 있으면 카운팅을 해주면 된다는 것을 떠올려 풀은 문제입니다.