Kotlin] 백준 1004번 문제 풀이

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

1004번: 어린 왕자

 

풀이

예시 그림을 보면 최단거리를 구하는것이 아니기 때문에, 점이 행성계에 존재하는지만 여부를 판단하면 된다.

즉, 해당 행성의 중심과 출발점(도착점)과의 거리(r)가 반지름(d)을 벗어나지 않는다면 되는 것이다.

r < d

r^2 < d^2

(출발점의 좌표 - 행성 반지름의 좌표)^2 < d^2

((x1-x2)^2+(y1-y2)^2)^2 < d^2

√((x1-x2)^2+(y1-y2)^2) < d

가 성립한다.

 

이 때, 주의해야 할 점은 행성계 하나에 출발점과 도착점이 있을 경우 굳이 해당값을 더하지 않아도 된다는 점인데,

그럼 전체 만나는 케이스에서 하나의 행성계에 점이 포함되는 케이스를 빼버리면 된다.

 

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

fun main(args: Array<String>) {
    question1004()
}

fun question1004() {
    var reader = BufferedReader(InputStreamReader(System.`in`))
    var case = reader.readLine().toInt()

    for(i in 1 .. case) {

        var goalCoor = reader.readLine().toString()
        var coorCount = reader.readLine().toInt()
        var meetPlanetCount = 0
        var isOne = 0

        var goalCoorArray = goalCoor.split(" ")
        var goalStart = arrayOf(goalCoorArray[0], goalCoorArray[1])
        var goalEnd = arrayOf(goalCoorArray[2], goalCoorArray[3])

        for (j in 1..coorCount) {
            var planetCoor = reader.readLine().toString()
            var planetCoorArray = planetCoor.split(" ")

			// 하나의 행성계에 모두 포함되는지 확인
            if (compareDimension(goalStart, planetCoorArray) && compareDimension(goalEnd, planetCoorArray)) {
                isOne++
            }
            
			// 전체 케이스 확인
            if (compareDimension(goalStart, planetCoorArray) || compareDimension(goalEnd, planetCoorArray)) {
                meetPlanetCount++
            }

        }

        println("${meetPlanetCount - isOne}")
    }
}

// 해당 좌표가 겹치는지 안겹치는지 확인.
fun compareDimension(goalArray : Array<String>, planetCoorArray : List<String>) : Boolean {
    var xLength = goalArray[0].toInt() - planetCoorArray[0].toInt()
    var yLength = goalArray[1].toInt() - planetCoorArray[1].toInt()

    var dimension = sqrt(xLength.toDouble().pow(2.0) + yLength.toDouble().pow(2.0))

    return dimension < planetCoorArray[2].toDouble()
}

 

 
++)

저놈의 런타임 에러가 무엇이냐.... 아 ㅋㅋ

멍청하게 문제를 잘못 이해해서 처음에 하나의 행성계에 포함되어 있으면 진입할 필요가 없다고 생각함..

그래서 하나의 행성이다! 라는 조건이 오면 break를 걸었는데, 잊어버린 것이다.. 

for문에 readline이 있다는 것을.. 그래서 입력 로직이 꼬이게 된것...

line에는 아직 행성계의 좌표가 남아있는데, 코드는 break되어 다시 for문 초기로 가고 케이스(var coorCount = reader.readLine().toInt()

)를 달라고 하니 당연히 1 1 0 <- 이런 형태를 Int로 변환시키지 못하면서 NumberFormatException이 난 것이다..

그 와중에 믿을 수 없어서 한 번 더 돌린 나새끼의 지능에 cheers...⭐️

 

+++)

Q. 그래서 왜 저렇게 많이 틀렸는데? 빠가사린가...

A. 앞에서 말했는데 >>멍청하게 문제를 잘못 이해해서 처음에 하나의 행성계에 포함되어 있으면 진입할 필요가 없다고 생각함..<<

여기에 꽂혀있어서 그랬음... 근데 생각해보니 이런 반례가 있는거임;

이 반례는 검은 행성계의 진입은 필요 없지만 파란 행성계의 진입 + 진출은 필요한 케이스임. 근데 저걸 코드로 일일히 빼고 앉아있는게 잘 안되서,

그래서 앞서 풀이에서 설명했지만 전체 반지름 > 길이 케이스(검은 원 + 파란 원)의 값에서 도착점과 시작점을 동시에 충족하는 케이스(검은 원)의 케이스를 빼버림.