[백준] 1004 어린왕자

이 문제는 백준-1002번 터렛과 유사한 문제이다.

출발점에서 도착점까지 이동할때 입력으로 주어진 원들의 경계를 최소한의 횟수로 거쳐 이동할수있는 횟수를 구하는 문제이다.

이 문제 역시 1002번과 동일하게 이상한 스토리로 작성해놓아 문제를 파악하는데 있어 약간의 걸리적거림이 있었다.

 

이 문제를 요약하면 출발점과 도착점이 주어졌을때 N개 만큼 주어진 원의 중심점으로 부터 거리를 케이스에 나눠주면 되는 문제다.

문제에서 말하는 행성은 이하 '원'으로 표현한다.

1) 출발점/도착점이 모두 원내부에 있는경우

위와 같은 상황인 경우가 출발/도착점이 모두 원 내에 있는 경우인데 (출발점과 도착점의 구분이 필요없다고 생각하여 동일한 색으로 칠함.)

이것은 표현하면 원의 중심으로부터 출발/도착점까지의 거리가 원의 반지름보다 작은 경우이고

식으로 표현하면 (x1-cx)*(x1-cx) + (y1-cy)*(y1-cy) < cr*cr 으로 표현이 가능하다.
x1,y1 : 출발점 / cx,cy,cr : 원의 중심위치 및 반지름, 도착점도 동일하게 계산 가능.

그림으로 보듯이 이런 경우에는 원의 경계를 지나칠필요가 없으므로 최소로 경계를 지나쳐야하는 횟수는 0이다.

 

2) 출발점/도착점이 모두 원 외부에 있는 경우

위의 1)의 케이스와 동일하다고 볼수있다.

출발점/도착점이 모두 원밖에 있으면 이 역시 굳이 원의 경계를 지나치지 않고도 출발점->도착점의 이동이 가능하다.

이 경우에도 역시 최소횟수는 0이다.

이를 수식으로 표현하면  (x1-cx)*(x1-cx) + (y1-cy)*(y1-cy) > cr*cr 과 같다.

 

3) 출발점/도착점 둘중 하나가 원의 안에 있는 경우.

이 경우가 반드시 경계를 지나쳐야하는 경우이다.

그림으로 보면 알듯이 최소한 1번은 지나쳐야 출발점에서 도착점의 이동이 가능하다.

이를 검증하기 위해 필요한 수식은 아래와 같다. x1,y1의 좌표를 출발점이라 하고 x2,y2의 좌표를 도착점이라 가정하면

 (x1-cx)*(x1-cx) + (y1-cy)*(y1-cy) > cr*cr

 (x2-cx)*(x2-cx) + (y2-cy)*(y2-cy) < cr*cr

출발점의 경우 원의 중심점과의 거리가 원의 반지름보다 크고,

도착점의 경우 원의 중심점과의 거리가 원의 반지름보다 작다면 반드시 경계를 지나치게 되있다.

당연하지만 출발점과 도착점이 반대가 되어도 성립한다.

이 경우가 바로 최소 횟수가 1이 되는 경우이다.

 

4) 결론

따라서 주어지는 원과 출발점/도착점간의 거리를 위와같은 3가지의 경우로 나누어 구현하면된다.

1) 2)의 케이스는 패스하고

3)의 케이스에서만 횟수를 1씩 늘려주면 된다.

참고로 sqrt를 쓰는것은 부동소수점의 문제가 있기 때문에 부정확한 결과를 가져올수있다.

이와같은 기하학 문제에서는 두점 사이의 거리를 구할때 sqrt를 쓰지말고 제곱한 채로 계산하는것이 더 정확하다.

 

 

자세한 코드는 아래의 깃에 올려놓았다.

 

https://github.com/manunite/Algorithm/blob/main/acmicpc/Acmicpc/Acmicpc/1004/no_1004.cpp

GitHub - manunite/Algorithm: 개인 알고리즘 문제풀이 한것 저장해놓는 레포지토리