[백준] BOJ 1004, 어린 왕자 파이썬 Python

서론

이번 포스팅에서는 백준 1004번 어린 왕자 문제를 풀겠다. 우선 어떻게 풀이 과정에 도달했는지에 설명하고 이어서 코드를 작성하는것으로 마무리할 예정이다. 백준 1004 문제를 보려면 여기로 가면 된다. 처음에 뭐야저거 했는데 쟤 그정도 아닙니다. 은하수 지도라고하는 참고용 도표만 없었어도 푼 사람 훨씬 많지 않았을까 싶다.

---

BOJ 1004 풀이 과정 1

문제를 보면 결국 요구하는게 출발점에서 도착점까지 몇개의 원을 통과해야 하는 지다. 은하수 지도를 보면 하나의 포물선으로 그려져 있으나 와리가리를 어떻게 해도 된다. 그냥 몇 개의 원을 지나는 지 구하기만 하면 되기 때문이다. 내가 이 문제를 풀었던 사고의 흐름을 보면 첫번째로 출발점 입장에서 왜 이 원은 지나야 하는지, 왜 이 원은 안 지나도 되는 지 생각했다. 그리고 깨달은 것은 출발점이 원 안에 포함됐을 때는 무조건 지나야 끝점을 만날 수 있다는 것이다. 그말인 즉슨 점이 원안에 포함되지 않는다면 굳이 지나지 않아도 된다. 설령 그 원이 출발점을 품고 있는 원 안에 있어도 말이다. 그렇게 출발점에서 중간 지점까지 원을 나왔다 쳤다. 그럼 이후에 이 출발점에서 끝점으로 가는 경로는 어떻게 구하지?라는 의문이 들었다. 그리고 깨달은 것은 끝점을 또 다른 출발점2라고 생각하고 얘도 밖으로 나오기 까지 몇개의 원을 통과하는지 구하면 되는거 아닌가?라고 생각했다. 그리고 출발점1에서의 통과 개수랑 출발점2(=끝점)에서의 통과 원 개수랑 합치면 되기 때문이다.

---

BOJ 1004 풀이 과정 2

BOJ 1004 풀이 과정 1을 코딩으로 옮기는 과정에 대해서 서술하도록 하겠다. 1) 시작점이나 끝점이 input으로 받는 원에 포함되는 지 판단한다. ( 점과 원점사이의 거리가 원의 반지름보다 짧으면 포함될 것이다.) 2) 그리고 이게 참이면 cnt+=1를한다. 그런데 1과 2를 판단하기 전에 하나 더 알아야 될 것은 두 시작과 끝 점이 어디에 있는 지다. 만약에 둘이 한 원 안에 있으면 나갈 필요가 없잖슴? 둘이 다른 원에 있을때만 True로 하고 싶었다. 이 때 필요한 연산이 XOR이다. 그래서 d보다 작은게 1개만 있을때만 True, 둘다 d보다 크거나 d보다 작을때는 False를 해서 count를 하지 않았다. 이 과정을 코드로 옮긴건 아래 코드블록을 참고하길 바란다.

---

BOJ 1004 코드

t  = int(input())
for _ in range(t):
    x1, y1, x2, y2 = map(int,input().split())
    n = int(input())
    cnt = 0 
    for _ in range(n):
        tmp_x, tmp_y, r = map(int,input().split())
        d_s = (x1-tmp_x)**2+(y1-tmp_y)**2
        d_e = (x2-tmp_x)**2+(y2-tmp_y)**2
        r = r**2
        if (d_s <= r) ^ (d_e <= r):
            cnt += 1
    print(cnt)