BOJ 1004 어린 왕자

이 문제는 알고스팟에서 봤던 문제와 비슷해서 그런지 내가 떠올린 풀이는 주어진 원들을 트리로 만들고 (주어진 두 점도 반지름의 길이가 0인 원으로 만들어 트리에 포함) 트리에서 그 두 원사이의 거리를 구하는 것인데... 이게 분명 쉬운 구현은 아닐텐데 (물론 내 기준으로..) 엄청나게 많은 사람이 풀었길래 맞은 사람 목록을 봤더니 코드가 매우 짧다...

분명 다른 풀이가 있을 것이다....
그 전에 내가 생각한 방법으로 풀어보자. 아.. 막상 풀려고 하니 문제가 되는 것이 root에 해당하는 원을 찾아야하는 것과, 또한 알고스팟 문제 처럼 하나의 트리로 이루어진 것이 아니라 이 문제에서는 여러 개의 트리가 나올 수 있어서 저 방법으로는 쉽지 않을 것 같다.

정말 이제 미련을 버리고 새로운 방법을 생각해 봐야겠다.... 가 아니라 다시 생각해보니 위의 방법으로도 할 수 있다. 한 개의 트리가 나오게 하면 된다. 바로 가장 큰 원으로 전체를 둘러싸면 되는 것이다. 일단 이 방법으로 풀어봐야지...

풀면서 예제조차 제대로 안 나와서 막막했는데, 종만북의 코드를 보니 내가 잘못한 부분이 있었다. 주어진 원들을 트리로 변환할 때, 어떤 원이 어떤 원의 자식이 되는지 판별하는 함수를 그냥 포함되면 무조건 자식으로 판별해서 무분별하게 이어지게 되고.. 그러다보니 dfs를 돌릴 때, 무한루프에 빠지게 되었다.

고쳐서 제출했는데 틀렸다... 반례를 찾기도 힘들고... 그래서 질문게시판도 보고 하다가.. 이 방법말고 좀 더 쉬운 방법으로 구현해 보고 AC를 받은 후에 랜덤 데이터를 돌려서 틀린 이유를 찾아내야 겠다.

방법은 그리 어렵지 않다. (내 스스로 생각한 건 아니지만...)
입력으로 들어오는 원들에 시작점과 끝점이 포함되는지 살펴보면서 포함되면 시작점, 끝점에 대해 각각 카운트를 해주는데, 만약 두 점다 포함된다면 카운트를 하지 않고, 최종적으로 시작점 카운트와 끝점 카운트를 더해주면 답이 될 것같다... AC를 받았다.

이제 원래 코드의 틀린 케이스를 찾아보자...
틀린케이스를 랜덤으로 생성하느라 코드도 짜고.. 이것 저것 실수도 많이하고(예를 들어 랜덤데이터는 100개인데, 배열을 10으로 잡아놔서 이상한 데이터가 생성됐다든지..) 정말 혼돈의 도가니였는데, 그 혼돈을 정리하고 계속 비교를 해봤지만.. 정말 수백번은 해본 것 같다. 그래도 계속 AC코드랑 답이 같게 나와서...진짜 지쳐서 포기할까 했지만 결국 저녁먹고 와서 또 해보다가 하나를 발견했다.

그리고 분석에 들어갔는데 수가 커서 좀 힘들었지만(수가 작으면 웬만해서는 안 나오길래.. 크게 잡았다. 원래의 문제의 범위대로..) 분석해서 이유를 알게되니 정말 허무했지만 한편으로는 왜 이 경우를 찾기가 힘들었는지 알 수 있었고, 기뻤다...일단 내가 트리로 푼 풀이가 틀린게 아니라 다른 데에 문제가 있었기 때문이다.

바로 트리를 만들 때, 이 문제에서 가장 큰 원으로 바깥을 둘러싸야 하는데, 입력으로 주어지는 모든 원을 둘러싸려면 매우 커야하고 다른 원들과 조금이라도 겹치면 안된다.
그래서 (2000, 2000)에 반지름 5000으로 잡았는데 분명 가로 세로만 봣을 때는 입력된 케이스들을 다 커버할만한 크기 같아보이지만 대각선 방향으로 보면 (-1000, 1000) 쯤에 있는 데이터를 완벽히 커버하지 못할 수 있어보였다... 그래서 얼른 (1100, 1100)에 반지름 6000으로 여유있게 해서 제출했더니.. 맞았습니다!!! AC를 받았다!!!

결국 트리를 만들어서 하는 풀이는 맞았지만 이 풀이를 위해 모든 원을 포함하는 큰 원을 설정하는 것에서 실수를...아니 전혀 생각도 못해서.. 매우 부주의했기 때문에 틀린 것이었다. 정말 생각도 못했을 뿐아니라 랜덤 데이터를 생성해도 저 범위를 넘는 데이터는 범위내에서 가장 큰 데이터가 나와야 하고, 처음에는 데이터 분석을 쉽게하려고 크기가 작은 데이터만 생성했기에... 이렇게 오랬동안 찾을 수 없었던 것이다.

어쩌면 그냥 못찾고 포기했을지도 모를 일이다. 정말 감사합니다!
힘내서 열심히 하자.