[BOJ] 어린 왕자 - 1004 (S3)

시간 제한	메모리 제한
2 초	128 MB

문제

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.

!https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/upload/201003/dfcmhrjj_113gw6bcng2_b.gif

빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.

위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 $(x_1, y_1)$과 도착점 $(x_2, y_2)$이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 $(c_x, c_y, r)$이 주어진다.

출력

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

제한

• $1000 ≤ x_1, y_1, x_2, y_2, c_y, c_x ≤ 1000$
• $1 ≤ r ≤ 1000$
• $1 ≤ n ≤ 50$
• 좌표와 반지름은 모두 정수

풀이

행성계를 꼭 통과해야 하는 조건을 먼저 찾는. 출발점이나 도착점이 행성계 안에 있을 경우 무조건 그 항성계를 통과해야 한다. 출발점이나 도착점을 포함하지 않고 있는 행성계는 어떻게든 피해갈 수 있기 때문이다.

한 점이 원 안에 포함되어있는지 확인하려면, 원의 반지름과 원의 중심과 그 점 사이의 거리를 비교하면 된다. 원의 반지름이 더 크다면 그 점은 무조건 원 안에 위치하게 되고, 원의 중심과 그 점 사이의 거리를 비교하면 그 점은 원 밖에 위치하게 된다.

코드

t = int(input())
for _ in range(t):
    cnt = 0
    x1, y1, x2, y2 = map(int, input().split())
    n = int(input())
    for _ in range(n):
        c_x, c_y, r = map(int, input().split())
        r = r ** 2
        dis1 = (c_x - x1) ** 2 + (c_y - y1) ** 2
        dis2 = (c_x - x2) ** 2 + (c_y - y2) ** 2
        if (dis1 < r and dis2 < r) or (dis1 > r and dis2 > r):
            continue
        else:
            cnt += 1
    print(cnt)

두 점 사이의 거리는 x, y 좌표 간의 차이의 제곱의 합에 제곱근을 취해 구할 수 있다. 위 코드에서는 연산을 조금 줄이기 위해 제곱인 상태에서 크기를 비교한다. 이 방법으로 출발점과 도착점을 포함하는 원들의 개수를 구해서 출력한다.