[BaekJoon] - 1004번 어린왕자

1004번: 어린 왕자

근무 하면서 푼 문제이다.

고민하다가 후임이 좋은 풀이법을 알려주었다.

 

출발점과 도착점이 주워지고, 행성의 개수가 7개라 하면 아래 표 처럼 만들 수 있다. 원은 (x-x1)**2 + (y-y1)**2 = r**2 방정식을 따르는데, 출발점을 각각의 행성에 대입해서 r**2 보다 작으면 출발점이 행성 안에 있다라는 뜻이 된다. 이때의 값은 O 라고 하고 아닐시 X라고 표시한다. 

	1번 행성	2번 행성	3번 행성	4번 행성	5번 행성	6번 행성	7번 행성
출발점	O	O	X	X	X	X	X
도착점	O	X	O	X	X	X	X

 

위 표를 분석해보면 다음과 같다.

1번 행성은 각각 O, O 결과이다. 이 뜻은 출발점과 도착점이 1번 행성 안에 존재 한다는 뜻이다. 즉 이러한 경우는 제외하면 된다. 2번째 행성은 O,X 결과이다. 이 뜻은 출발점은 2번 행성 안에 있지만, 도착점은 밖에 있다는 뜻이다. 즉, 출발점과 도착점을 잇는다면, 무조건 한 점으로 만나게 된다. 

 

그럼 위 표의 결과를 각각 XOR 연산을 하면 최종적인 결과를 얻어 낼 수 있을 것이다. 위 표의 결과는 2 이다.

 

아래는 python3 으로 코드를 구현한 것이다.

 

# -*- coding: utf-8 -*-
def isInCircle(point, circle):
    answer = list()
    
    for c in circle.values():
        result = eval(c[0].format(point[0], point[1]))
        
        if result < c[1]:
            answer.append(1)
        else:
            answer.append(0)
    return answer


if __name__ == "__main__":
    r = list()
    # 테스트 케이스의 개수 T
    testCase_count = int(input(""))
    
    for count in range(0, testCase_count):
        #각각의 테스트 케이스에 대한 출발점과 도착점 입력
        start_end = list(map(int, input("").split(" ")))
        
        # 출발점과 도착점을 분리하여 저장
        startPoint = [start_end[0],start_end[1]]
        endPoint = [start_end[2],start_end[3]]
        
        # 행성의 개수 n
        n = int(input(""))
        circle = dict()
        for i in range(0,n):
            input_data = list(map(int ,input("").split(" ")))
            circle[i] = ["({} - ("+str(input_data[0])+")) ** 2 + ({} - ("+str(input_data[1])+")) ** 2", int(input_data[2]) ** 2]
        
        result1 = isInCircle(startPoint, circle)
        result2 = isInCircle(endPoint, circle)
        
        count = 0
        for i in range(0, n):
            if result1[i] ^ result2[i] == 1:
                count += 1
        
        r.append(count)
        
    for i in range(0,len(r)):
        print(r[i])