[알고리즘] 어린왕자 10004 파이썬 풀이

 

백준의 10004번째 문제인 어린왕자는 한 점에서 시작해서 다른 점으로 이동할 때, 적어도 통과해야 하는 원의 개수를 찾는 문제입니다. 이 문제는 점에서 다른 점을 이동하므로 문제를 다른 방식으로 해석하지 않는다면 복잡하게 풀 수 밖에 없습니다. 

 

몇가지 관찰을 통해서 다음과 같은 사실을 알 수 있습니다. 

 

아래 그림의 경우, 한 점은 반드시 하나의 원을 빠져나가야 합니다. (1개) 

또한 어떠한 방향으로 가던지 다른 점에 통과하기 위해서는 반드시 2개의 점을 지나야 합니다. (2개) 

따라서 아래 그림의 경우 반드시 3개의 원을 지나게 됩니다. 

여기서 3개의 원은 점을 포함하고 있는 원이라는 특징이 있습니다.

 

따라서 일반적으로 최소 개수의 원은 각 점을 내부에 포함하고 있는 원의 개수가 됩니다. 

만일 두 점을 동시에 포함하고 있는 점이 있다면, 그 원부터는 제외하면 되겠죠? 

어린왕자는 한 점에서 다른 점으로 이동한다. 

# 포함하는 원들을 각각 찾는다. 
# 원의 번호가 같아 지는 놈을 찾는다. 
# 그 전까지 더하기
 
 
 
def isInCircle(x,y, circle):
    if (circle[0]-x)**2 + (circle[1]-y)**2 < circle[2]**2:
        return True
    else:
        return False
 
T  = int(input())
for i in range(T):
    x1,y1,x2,y2 = map(int, input().strip().split())
    num_circle = int(input())
    circles = [[0,0, 2000]]
    for _ in range(num_circle):
        circles.append(list(map(int, input().strip().split())))
    C1 = []
    C2 = []
    for i, c in enumerate(circles):
        if isInCircle(x1,y1, c):
            C1.append(i)
        if isInCircle(x2,y2, c):
            C2.append(i)
    # C1,C2에 공통인 부분의 개수를 찾는다. 
    count = 0
    for c in C1:
        if c in C2:
            count +=1
    print(len(C1)+len(C2)- count*2)