[python] 백준 1004 : 어린 왕자

행성계를 최소횟수로 이탈/진입해서 장미까지 닿으려는 우리의 어린왕자.. 앞에 원이 가로막고있는경우는 우회해서 가면됩니다. 그럼 우회를 하지못하는경우는 어떤 경우일까요? 출발점 혹은 도착점이 어떤 원 내부에있는경우 점에 도달하기위해선 경계를 뚫고가야겠죠. 만약 두점이 같은 계(System)안에 있다면? 그건 상관없습니다. 경계를 굳이 나갔다 들어올필요가 없죠.

 

문제해결을 위한 논리구조를 정리해보면 

입력받은 원(행성계)이 출발점/도착점을 동시에 포함하면 -> None, 출발점/도착점이 모두 원 밖에있을때 -> None

어느 한점'만' 행성계안에 있을때 -> cnt+=1. 조건에 행성계의 경계위에있는 경우는 입력받지 않는다고 되어있으므로 이정도만 생각하면 될것같네요.

그렇다면 원안에 있는지 밖에있는지는 어떻게 판단할까요? 원은 한 점(중심)으로부터 거리가 일정한 점들의 집합이죠. 거리값이 '반지름'이 되는거구요. 그렇다면 중심에서 출발점/도착점까지의 거리가 반지름보다 크다면 원밖에, 작다면 원안에 있는걸로 판단할수 있겠네요.

 

T=int(input())

list_a=[]
list_b=[]
list_r=[]

for _ in range(T):
    x1,y1,x2,y2=map(int,input().split())
    n=int(input())
    cnt=0
    
    for i in range(n):
        a,b,r=map(int,input().split())
        
        list_a.append(a)
        list_b.append(b)
        list_r.append(r)

        dist_start=(((x1-list_a[i])**2)+((y1-list_b[i])**2))**(1/2)
        dist_end=(((x2-list_a[i])**2)+((y2-list_b[i])**2))**(1/2)
        radius=list_r[i]
        
        if dist_start>radius and dist_end>radius:
            None

        elif dist_start<radius and dist_end<radius:
            None

        else:
            cnt+=1

    print(cnt)

출발점(x1,y1)과 도착점(x2,y2)을 입력받고, n개의 행성계 (a,b,r)을 입력받아 각각 리스트에 추가합니다. for문으로 리스트에 저장된 모든 행성계에 대해 중심으로부터 출발점/도착점까지의 거리와 반지름의 크기 대소비교를 해줍니다. 그 결과 둘다 반지름보다 크거나(해당 행성계에 출발/도착점 모두 미포함) 작은경우(해당 행성계에 출발/도착점 모두 포함)는 None, 그 밖의 경우는 한쪽만 포함되는 경우라 판단하여 else처리로 cnt+=1을 해줬습니다 그런데..

이런 썅!!!!!!! 예제 입력을 해보니 다른값이 나와요!

 

의심해볼만한 경우는 distance를 구할때 혹시 float가 아닌 정수형으로 나오나..?

음.. 아니네요. 제가 굳이 int를 쓰지않는이상 계산되는데로 나오겠죠. 예제출력에선 분명 5가 출력되던데 왜 3이나올까요..? 일단 진짜 5가 맞는지 의심해봅시다.

지오지브라를 이용해 예제를 급하게 입력해봤습니다. 5가 맞네요. 논리구조가 잘못된걸까요? 이럴땐 코드를 파트별로 나눠서 보든 입력값을 한개의 테스트케이스에 대해 하나하나 넣어보든 암튼 부분별로 나눠서 분석해보면 어디서 잘못됐는지 판단할수있습니다. 그림과 비교해본결과 논리구조엔 문제가 없어요

 

앗 ! 그러던중 발견한 특이점.. 테스트케이스에 따라 같은 입력이라도 값이 이상해진다..? 빨간색 표시한 부분을 보시면 출발점/도착점의 좌표와 각 행성계의 중점과 반지름 등 입력값은 모두 같은데 출력값이 다릅니다. 위에는 테스트케이스 3개로 한번에 입력받는경우고 아래는 테스트케이스 1개로 개별로 입력받는겁니다. 테스트케이스를 입력받는 for문에서 뭔가 오류가 발생한거같습니다.

 

테스트케이스가 1일때는 값이 잘 나오지만 여러개일때는 값이 이상하게 나온다는것은 아마 이전 테스트케이스가 다음 테스트케이스에 어떠한 영향을 미치고있다는 킹리적갓심을 해볼수있습니다. 각 테스트케이스는 철저히 독립적인 계산이 이뤄져야하죠. 코드를 보니까 바로알겠네요.. 테스트 케이스 for문 밖에 리스트가 정의되어있습니다. 이렇게되면 1개의 테스트케이스가 종료된후 다음 테스트케이스에 대한 계산을 수행할때 이전에 리스트에 입력된값이 초기화되지않고 누적되어 영향을 미칩니다. for문 안에 빈 리스트를 넣어줘 한번의 테스트케이스가 종료될때마다 리스트를 초기화시켜야합니다.

 

T=int(input())

for _ in range(T):
    x1,y1,x2,y2=map(int,input().split())
    n=int(input())
    cnt=0
    
    list_a=[]
    list_b=[]
    list_r=[]
    
    for i in range(n):
        a,b,r=map(int,input().split())
        
        list_a.append(a)
        list_b.append(b)
        list_r.append(r)

        dist_start=(((x1-list_a[i])**2)+((y1-list_b[i])**2))**(1/2)
        dist_end=(((x2-list_a[i])**2)+((y2-list_b[i])**2))**(1/2)
        radius=list_r[i]
        
        if dist_start>radius and dist_end>radius:
            None

        elif dist_start<radius and dist_end<radius:
            None

        else:
            cnt+=1

    print(cnt)

테스트 케이스에 대한 for문안으로 리스트정의 파트를 넣으니 예제 입/출력과 일치하게 나오네요. for문의 동작에 대해 약간 집중을 못한듯... 그래도 출력값이 잘못됐을때 부분부분 따져서 분석했기에 오류를 빠르게 잡을수있었습니다.

전에 말씀드렸다시피 문제를 풀면서 동시에 글을쓰기때문에 중간에 헤맨부분도 같이 기록되는 머쓱함.....머쓱타드....