[백준/파이썬] 1004번 문제 '어린 왕자'

백준 1004번 문제 '터렛'

c

1004번: 어린 왕자

 

 

문제

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

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

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

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다. 입력제한은 다음과 같다. (-1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000, 1 ≤ r ≤ 1000, 1 ≤ n ≤ 50)

좌표와 반지름은 모두 정수이다.

 

출력

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

 

예제 입력

 

 

 

문제 풀이

 

전체 소스 코드 보기

# 테스트 케이스 개수
T = int(input())

for _ in range(T):
    # 출발점 도착점
    x1, y1, x2, y2 = list(map(int, input().split()))
    # 행성계의 개수
    n = int(input())
    count = 0
    for _ in range(n):
        cx, cy, cr = map(int, input().split())
        dis1 = (x1 - cx)**2 + (y1 - cy)**2
        dis2 = (x2 - cx)**2 + (y2 - cy)**2
        pow_cr = cr**2
        
        if pow_cr > dis1 and pow_cr > dis2:
            pass
        elif pow_cr > dis1:
            count += 1
        elif pow_cr > dis2:
            count += 1
            
    print(count)

 

이번 문제는 출발점에서 도착점까지 이동할 때, 중간중간에 위치한 행성들에 최소한으로 진입/이탈하는 문제이다.

사실 중간에 있는 행성을 피하는건 어린 왕자의 우주선이 알아서 피해서 운행하면 되기 때문에,

정말 어쩔 수 없이 행성을 접하는 경우는 출발점이나 도착점이 행성의 내부에 위치한 경우이다.

 

 

'출발점에서 도착점까지 이동하는데 접하는 행성의 수'

 

위 그림을 보면 우주선이 다른 행성들을 잘 피해가지만, 이미 엄청 큰 행성 내부에 위치해 있기 때문에

해당 행성에서 이탈하면서 이탈 횟수가 1번 추가된다.

그리고 도착점을 보면 2개의 행성 내부에 위치해있기 때문에 어쩔 수 없이 행성 2개에 진입을 해야한다.

따라서 진입 횟수가 2회 추가된다.

'총 진입/이탈 횟수는 3회'가 되는 것이다.

 

결론적으로 총 진입/이탈 횟수가 추가되는 경우는

출발점이나 도착점이 행성 내부에 위치한 경우 (출발점과 행성 중심과의 거리가 행성 반지름보다 작은 경우) 이다.

단, 출발점과 도착점이 모두 행성 내부에 위치해 있다면 (행성 중심과의 거리가 '모두' 행성의 반지름보다 작은 경우)

특정 행성을 들릴 필요가 없기 때문에 총 진입/이탈 횟수는 0이 된다.

 

'출발점과 도착점이 모두 행성 내부에 있어 진입/이탈이 필요 없는 경우'

 

이제 이 개념을 코드로 구현해보자.

 

# 테스트 케이스 개수
T = int(input())

 

우선, 테스트 케이스를 input() 메소드를 통해 입력받는다.

 

for _ in range(T):
    # 출발점 도착점
    x1, y1, x2, y2 = list(map(int, input().split()))
    # 행성계의 개수
    n = int(input())
    count = 0
    for _ in range(n):
        cx, cy, cr = map(int, input().split())
        dis1 = (x1 - cx)**2 + (y1 - cy)**2
        dis2 = (x2 - cx)**2 + (y2 - cy)**2
        pow_cr = cr**2
        
        if pow_cr > dis1 and pow_cr > dis2:
            pass
        elif pow_cr > dis1:
            count += 1
        elif pow_cr > dis2:
            count += 1
            
    print(count)

 

for문을 통해 T만큼 반복하여 테스트를 진행할 수 있도록 하고, 출발점과 도착점을 입력받도록 한다.

그 다음으론, 변수 n에 '행성계의 개수'를 입력받고, 총 진입/이탈 횟수를 저장할 count 변수를 선언해준다.

그리고 n개의 행성계의 좌표와 반지름을 n번만큼 반복하여 입력받는데, 각 행성의 좌표와 반지름은 각각 cx, cy, cr이라는 변수에 입력받는다.

 

'점과 점 사이의 거리를 구하는 공식'

 

변수를 입력받았다면, 위 공식을 통해 행성의 중심 좌표와 출발점, 시작점 사이의 거리를 구해준다.

만약 두 거리가 모두 행성의 반지름보다 작다면, 출발점과 시작점 모두 행성 내부에 있기 때문에 다른 행성을 진입할 필요가 없기 때문에 그냥 pass해준다.

그렇지 않고 두 지점 중에 하나만 행성 내부에 있는 경우에는 행성에서 진입 또는 이탈을 할 필요가 있기 때문에

총 진입/이탈 횟수인 count 변수의 값을 1회 늘려준다.

그렇게 반복문이 끝나고 count를 출력하면 문제는 끝이 난다.

 

---

 

 

👍클릭으로 구독하기👍

 

(이해가 다소 힘들거나, 틀린 부분이 있다면 댓글 부탁드리겠습니다! 😊)

💖도움이 되셨다면 '구독'과 '공감' 부탁드립니다!💖