BaekJoon 1004번: 어린 왕자 (Python)

---

1. Problem

---

2. Solution

* My solution

T = int(input())
for i in range(T):
    loc = list(map(int, input().split()))
    n = int(input())
    lst = list(list(map(int, input().split())) for j in range(n))
    result = []
    distinct = [0] * n
    for j in range(n):
        count = 0
        for k in range(2):
            if (loc[2 * k] - lst[j][0]) ** 2 + (loc[2 * k + 1] - lst[j][1]) ** 2 < lst[j][2] ** 2:
                count += 1
        result.append(count)
    for j in range(len(result)):
        if result[j] == 1:
            distinct[j] = 1
    print(sum(distinct))

* Other Solution

import sys

for _ in range(int(sys.stdin.readline())):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())

    answer = 0
    for _ in range(int(sys.stdin.readline())):
        cx, cy, r = map(int, sys.stdin.readline().split())

        d1, d2 = ((x1-cx)**2 + (y1-cy)**2)**0.5, ((x2-cx)**2 + (y2-cy)**2)**0.5
        if (d1 < r and d2 > r) or (d1 > r and d2 < r):
            answer += 1

    print(answer)

---

3. Detail

어린 왕자 문제는 n개의 반지름 r을 가진 행성계의 중점 (x, y) 좌표가 2차원 좌표계 상에 놓여져 있고, 출발점 ($x_{1}$, $y_{1}$)이 도착점 ($x_{2}$, $y_{2}$)에 도착할 때까지의 행성계의 최소 진입/이탈 횟수를 구하는 문제이다.

즉, n개의 행성계마다 출발점과 도착점 2개의 점 중에 1개의 점은 행성계 내에 있고, 나머지 1개의 점은 행성계 밖에 있는 경우의 수를 찾는 문제이다.

아래 그림은 행성계의 수가 8개일 경우의 예시이다. 아래 그림을 살펴보자.

위의 그림에서 진입과 이탈의 횟수는 총 5회이다. 출발점과 도착점 2개의 점 중 행성계 내에 몇 개가 있는지 살펴보자.

행성계 1번 -> 출발점과 도착점 모두 행성계 밖에 위치 -> 0개
행성계 2번 -> 출발점은 행성계 내에 위치, 도착점은 행성계 밖에 위치 -> 1개
행성계 3번 -> 출발점은 행성계 내에 위치, 도착점은 행성계 밖에 위치 -> 1개
행성계 4번 -> 출발점은 행성계 내에 위치, 도착점은 행성계 밖에 위치 -> 1개
행성계 5번 -> 출발점과 도착점 모두 행성계 밖에 위치 -> 0개
행성계 6번 -> 출발점과 도착점 모두 행성계 밖에 위치 -> 0개
행성계 7번 -> 출발점은 행성계 밖에 위치, 도착점은 행성계 내에 위치 -> 1개
행성계 8번 -> 출발점은 행성계 밖에 위치, 도착점은 행성계 내에 위치 -> 1개

이 것을 차례대로 result라는 list로 나타내면 [0, 1, 1, 1, 0, 0, 1, 1]이 된다. 이때, list의 각 index의 값들은 0 ~ 2 사이의 값 중 하나이다. 그러므로 우리는 출발점과 도착점 2개의 점 중 1개의 점은 행성계 안에 위치하고, 나머지 1개의 점은 행성계 밖에 위치하는 경우의 수를 구해야하기 때문에 if result[j] == 1라는 조건식을 이용하여 1일 경우에만 distinct라는 list의 해당 index의 값을 1로 바꿔준다. for문이 종료되면 distinct list는 [0, 1, 1, 1, 0, 0, 1, 1]이 된다. 최종적으로 print(sum(distince))를 하면 출발점과 도착점 2개의 점 중에 1개의 점은 행성계 내에 있고, 나머지 1개의 점은 행성계 밖에 있는 경우의 수가 나오게 되고, 이는 곧 최소 진입/이탈 횟수가 된다.