[Silver III] 어린 왕자 - 1004

문제 링크

성능 요약

메모리: 32412 KB, 시간: 40 ms

분류

기하학, 수학

제출 일자

2025년 2월 17일 21:47:47

문제 설명

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

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

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

입력

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

출력

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

---

문제 풀이

문제 분석

이 문제는 어린 왕자가 출발점에서 도착점까지 이동할 때, 행성계(원)의 경계를 통과해야 하는 최소 횟수를 구하는 것입니다. 행성계는 서로 겹치거나 접하지 않으며, 출발점과 도착점은 어떤 행성계의 경계 위에도 있지 않습니다. 각 행성계는 중심(cx, cy)과 반지름 r로 주어집니다. 우리는 출발점과 도착점이 각각 몇 개의 행성계 내부에 있는지 확인하고, 두 점 모두 내부에 있는 행성계는 경계를 crossing하지 않아도 되므로 제외한 나머지 행성계 수의 합이 정답이 됩니다.

접근 방법

이 문제를 해결하기 위해 기하학적 조건 검사와 집합 연산을 사용합니다. 두 점(출발점, 도착점)이 특정 원의 내부에 있는지 확인하려면, 점과 원 중심 사이의 거리 제곱이 반지름 제곱보다 작은지 검사하면 됩니다(거리를 제곱해서 sqrt 연산을 피해도 됩니다). 이렇게 각 점에 대해 포함된 원의 인덱스를 저장한 후, 두 집합의 합집합 크기에서 교집합 크기를 빼면(즉, A ∪ B - A ∩ B = A差B + B差A), 최소 crossing 횟수가 나옵니다. 이 방법은 O(n) 시간에 각 테스트 케이스를 해결할 수 있어 효율적입니다.

구현 설명

1. 입력 읽기 및 초기화

테스트 케이스 수 t를 읽고, 각 케이스마다 출발점 (x1, y1), 도착점 (x2, y2)를 읽습니다. 이후 행성계 개수 n을 읽고, n개의 행성 정보 (cx, cy, r)를 차례로 입력받습니다.

2. 각 점의 행성계 내부 포함 여부 검사

각 행성계마다 출발점이 원 내부에 있는지 검사합니다: (x1-cx)^2 + (y1-cy)^2 < r^2이면 출발점은 이 원 내부입니다. 동일하게 도착점도 검사합니다. 각각에 대해 포함된 행성계의 인덱스를 stack1(출발점)과 stack2(도착점) 리스트에 저장합니다.

3. 최소 crossing 횟수 계산

answer = len(stack1) + len(stack2)로 시작합니다. 이는 출발점과 도착점이 각각 독립적으로 crossing해야 할 수를 더한 것입니다. 그러나 두 점 모두 같은 원 내부에 있다면 그 원은 crossing하지 않아도 되므로, stack1과 stack2의 교집합에 속한 인덱스마다 answer에서 2를 빼줍니다.결국 answer = (stack1만의 원 수) + (stack2만의 원 수)가 됩니다.

4. 결과 출력

계산된 answer를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: 각 테스트 케이스에서 n개의 행성계에 대해 두 점에 대한 간단한 산술 연산(제곱 비교)을 수행하므로 O(n)입니다. 테스트 케이스가 t개이므로 총 O(t * n)입니다.
• 공간 복잡도: 각 테스트 케이스에서 stack1과 stack2에 최대 n개의 인덱스를 저장하므로 O(n)입니다. 추가적인 큰 자료구조를 사용하지 않습니다.

핵심 포인트

1. 행성계 내부 판정: 점이 원의 내부에 있는지는 점과 원 중심 사이의 거리 제곱이 반지름 제곱보다 작은지로 판단합니다. 이때 sqrt 연산 없이 제곱만 비교해도 됩니다.
2. 중복 제거 전략: 출발점과 도착점이 모두 같은 원 내부에 있으면 그 원의 경계를 crossing하지 않아도 되므로, 두 집합의 교집합을 찾아 해당 원의 기여도를 2에서 0으로 줄입니다.
3. 단순한 집합 연산: 리스트나 집합을 이용해 포함된 원의 인덱스를 모으고, 교집합을 빼는 것으로 최소 crossing 횟수를 효율적으로 계산할 수 있습니다. 복잡한 경로 계산은 필요 없습니다.

풀이 코드

import sys

t = int(sys.stdin.readline())

for i in range(t):
    x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
    n = int(sys.stdin.readline())
    stack1 = []
    stack2 = []
    for i in range(n):
        dx,dy,dr = map(int, sys.stdin.readline().split())
        dist1 = (x1-dx)**2+(y1-dy)**2
        dist2 = (x2-dx)**2+(y2-dy)**2
        if (dr**2 > dist1):
            stack1.append(i)
        if(dr**2 > dist2):
            stack2.append(i)

    answer = len(stack1) + len(stack2)
    for i in stack1:
        if i in stack2:
            answer-=2
    
    print(answer)