BOJ 1004 어린 왕자 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

어린왕자의 우주선은 행성계 간의 이동을 최대한 피해서 여행해야 함.

• 빨간 실선: 출발점에서 도착점가지 도달하는 데 있어 행성계 진입, 이탈 횟수를 최소화하는 경로
• 원: 행성계의 경계

적어도 3번의 행성계 진입/이탈 필요

→ 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하기.

행성계 경계가 맞닿거나 서로 교차하는 경우, 출발점/도착점이 행성계 경계에 걸쳐진 경우 x

• 입력

첫번째 줄) 테스트 케이스 개수 T

그 다음 줄) 각각의 테스트 케이스에 대해 첫째 줄에 출발점(x1, y1)과 도착점(x2, y2) 주어짐.

두번째 줄) 행성계 개수 n

세번째 줄~n번째 줄) 행성계 중점과 반지름(cx, cy, r)

• 출력

각 테스트 케이스에 대해 행성계 진입/이탈 횟수의 최솟값.

• 제한
  • 1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000
  • 1 ≤ r ≤ 1000
  • 1 ≤ n ≤ 50
  • 좌표와 반지름은 모두 정수

두 번째 단계 (문제 핵심 파악)

최대한 원을 안 닿게 하는게 좋다.

따라서 어떤 경우에 반드시 원을 지나야 하는지, 지나지 않아도 되는지 생각해보자.

1. 시작점, 출발점이 둘 중 하나만 행성계 내부에 있을 경우

   해당 행성계를 반드시 지나가야 함.

2. 시작점, 출발점이 둘 다 행성계 내부 or 외부에 있을 경우

   행성계를 안 지나가도 됨.

그렇다면, 원의 내부에 점이 있는지 아닌지 판별하는 방법?

행성계 중점과 시작점 or 출발점 사이의 거리 > 반지름 : 행성계 외부의 점.

행성계 중점과 시작점 or 출발점 사이의 거리 < 반지름 : 행성계 내부의 점.

→ 모든 원에 대해서 반드시 지나야 하는 지 여부를 검사하고, 지나야 하는 원의 개수 출력.

코드 작성

import math

t = int(input())

for _ in range(t):  # 테스트 케이스
    # 출발점(x1, y1)과 도착점(x2, y2)
    x1, y1, x2, y2 = map(int, input().split())

    n = int(input())  # 행성계 개수
    ans = 0  # 원을 지나는 개수

    for _ in range(n):
        cx, cy, r = map(int, input().split())
        # 거리 계산
        start_to_mid = math.sqrt((x1 - cx) ** 2 + (y1 - cy) ** 2)
        fin_to_mid = math.sqrt((x2 - cx) ** 2 + (y2 - cy) ** 2)
        # 행성계 내부의 점
        # 출발점
        if start_to_mid < r and fin_to_mid < r:  # 둘다 안에 있을 경우 행성계를 안지나가도 됨.
            pass
        elif start_to_mid < r:
            ans += 1
        elif fin_to_mid < r:
            ans += 1
    print(ans)

느낀점

1. or의 허점(?)

import math

t = int(input())

for _ in range(t):  # 테스트 케이스
    # 출발점(x1, y1)과 도착점(x2, y2)
    x1, y1, x2, y2 = map(int, input().split())

    n = int(input())  # 행성계 개수
    # 지나야 하는 원의 개수
    ans = 0
    for _ in range(n):
        cx, cy, r = map(int, input().split())
        # 행성계 내부의 점
        if math.sqrt((x1 - cx) ** 2 + (y1 - cy) ** 2) < r or math.sqrt((x2 - cx) ** 2 + (y2 - cy) ** 2) < r:
            ans += 1
    print(ans)

위와 같이 처음에는 행성계 내부의 점의 조건식을 or로 했는데, 틀렸다고 해서 의아했다.

왜지? 한 20분 고민했나..

or이면 조건식1이 참이거나 조건식2이 참이거나 혹은 둘다 참일때도 참인거다.

따라서 각각을 조건문으로 걸어주고, and 조건일때는 pass 시켜야 함을 깨달았다.

기본이 가장 중요하다니까..
2. 그림 보고 쫄지 말고 이용할 개념 생각해보기
그리고 문제 그림보고 쫄았는데(원과 곡선) ps에서 사용된 개념은 수학에서 기초적인 두 점 사이의 거리 뿐이다. 쫄지 말자.

• 참고한 블로그
  (https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221048019075)](https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221048019075)