[python] Baekjoon 1004 : 어린 왕자

문제 - Baekjoon 1004 : 어린 왕자

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

1004번: 어린 왕자

핵심

• 문제: 어린 왕자가 은하수를 여행하며 행성계의 경계를 최소한으로 지나가야 하는 횟수 계산하기

내용

• 이 문제는 행성계의 경계를 최소한으로 지나가는 경로를 찾는 것입니다. 출발점과 도착점의 좌표가 주어지고, 여러 행성계의 중심 좌표와 반지름이 주어질 때, 출발점에서 도착점까지 이동하면서 행성계의 경계를 몇 번 지나치는지 계산하는 문제입니다. 기하학적 계산과 조건 판별이 필요한 문제입니다.

study coding

접근 방법

1. 좌표 입력 처리: 출발점과 도착점의 좌표를 입력받습니다.
2. 행성계 정보 입력 처리: 각 행성계의 중심 좌표와 반지름을 입력받습니다.
3. 경계 진입/이탈 여부 판단: 출발점과 도착점이 각 행성계의 경계 내부에 있는지 판단합니다.
4. 진입/이탈 횟수 계산: 출발점과 도착점이 행성계 경계 내부에 위치할 때만 진입 또는 이탈로 간주합니다.
5. 결과 출력: 각 테스트 케이스에 대해 계산된 진입/이탈 횟수를 출력합니다.

코드

def is_inside(x, y, cx, cy, r):
    return (x - cx)**2 + (y - cy)**2 < r**2

# 입력 처리
T = int(input())
for _ in range(T):
    x1, y1, x2, y2 = map(int, input().split())
    n = int(input())
    count = 0

    for _ in range(n):
        cx, cy, r = map(int, input().split())
        if is_inside(x1, y1, cx, cy, r) != is_inside(x2, y2, cx, cy, r):
            count += 1

    print(count)

풀이

• 각 행성계의 경계 내부에 출발점과 도착점이 있는지 판단하는 함수 is_inside를 사용합니다.
• 출발점과 도착점이 행성계 경계 내부에 서로 다르게 위치할 때마다 카운트를 증가시킵니다.
• 계산된 카운트를 출력하여 행성계의 경계를 지나는 최소 횟수를 제시합니다.

참고할 만한 자료

1. 기하학적 계산: 좌표와 반지름을 사용한 기하학적 위치 판별 방법에 대한 자료입니다.
2. 조건문 사용법: Python에서 조건문을 사용하는 방법에 대한 자료입니다.
3. 입출력 및 반복문: Python에서 효율적인 입출력과 반복문 사용 방법에 대한 자료입니다.

space

추천 링크:

• 기하학적 계산 기초: Khan Academy - Basic Geometry
• Python 조건문 사용법: W3Schools Python Conditions
• Python 입출력 및 반복문: Python 공식 문서