[BOJ] 백준 1004 어린 왕자

문제 링크

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

맞은 사람 목록을 보면 해당 풀이보다 더 간단한 풀이가 존재하는 것 같다. 어쨌든 내 경우엔 이렇게 풀었다.

---

좌표평면 위의 원(행성계)들이 주어지고 출발점과 도착점이 주어졌을 때, 출발점에서 도착점으로 가는 동안 원을 뚫고 가는 횟수를 최소화해야 한다.

문제에서 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다."라는 조건을 주었기 때문에 쉽게 풀 수 있다.

풀이에 앞서 '점 $X$ 또는 원$X$가 원$C$에 포함된다'라는 말을 '$X$가 $C$의 경계에 걸치거나 교차하지 않으면서, $C$ 내부에 있는 상태' 라고 하겠다.

1) 출발점이나 도착점이 여러 개의 원에 포함된다면 그 원 중에서도 작은 원은 항상 큰 원에 포함된다. 

2) 출발점과 도착점을 동시에 포함하는 가장 작은 원 $C$를 찾으면 그보다 큰 원은 생각하지 않아도 된다. 1)에 의해 출발점에서 도착점까지 $C$내에서 항상 다른 원을 거치지 않고 갈 수 있기 때문이다.

3) 어떤 원 $C$가 출발점이나 도착점중 하나를 포함하고 있으면, 출발점에서 도착점으로 가기 위해 그 원을 항상 지나야 한다.

  

그림과 같은 상황에는 1)과 2)가 성립하지 않지만, 이런 경우가 없음이 명시되어 있다.

따라서 답은 출발점과 도착점을 동시에 포함하는 가장 작은 원보다 작은 원 중, 출발점 또는 도착점을 포함하는 각 원의 개수이다. 만약 동시에 포함하는 원이 없다면 한 점을 포함하는 모든 원에 대해 생각하면 된다.

위의 정보를 바탕으로 문제를 풀어보자.

우선 원이 시작점이나 끝점을 포함하는지 확인한다. 이를 확인하려면 점과 원 중심과의 거리 $d$와 원의 반지름 $r$을 비교하면 된다.

빨간색 점을 기준으로

$d1 < r1$이고 점이 원에 포함되어 있다.

$d2 > r2$이고 점은 원에 포함되지 않는다.

$d = r$인 경우는 점이 원 경계에 놓여있는 경우인데, 이는 주어지지 않으므로 생각하지 않아도 된다.

시작점을 포함하는 원들의 배열 $s$와, 끝점을 포함한 원들의 배열 $e$를 두고, 오름차순으로 정렬한다. 그후 $s$와 $e$ 에서 반지름이 작은 원 순서대로 탐색한다. 탐색되는 원들은 모두 경로상 지나가야 하는 원들이다.

이때, $s[i]$와 $e[j]$가 같은 원이라면 2)에서 말한 출발점과 도착점을 동시에 포함하는 가장 작은 원이므로 탐색을 종료한다. 만약 s나 e중 하나라도 끝까지 탐색했다면 동시에 포함하는 원이 없다는 말이므로 나머지 배열의 남은 부분을 답에 더해준다.

디테일한 부분은 코드를 참고하자.

정답 코드