[백준] 1002번 : 터렛(두 원의 위치 관계)- 파이썬[Python]

문제

 

1002번: 터렛

 

 

풀이

 

일단 두 좌표의 한 지점까지의 거리가 나오며 거리의 변수가 r인 것으로 보아 원을 이용해서 푸는 문제임을 알 수 있다.

각 좌표(x,y)에서 r값을 반지름으로 하는 원을 그려서 겹치는 지점의 개수를 출력하는 문제이다. 

즉, 두 원의 위치관계에 대한 조건을 이용해서 문제를 풀어야 한다.

과거 고등학교 시절 두 원의 위치관계에 대해서 공부했던 기억이 있었지만, 정확하게 기억은 나지 않았다.

그래도 혼자서 문제를 해결하기 위해 코드를 짜보았다.

 

 

피타고라스 정리를 이용해서 (x2-x1)^2+(y2-y1)^2 과(r1+r2)^2을 비교하는 코드를 작성했다.

두 값이 같으면 한 점에서 만나는 관계니까 1 출력

(r1+r2)^2 값이 더 크면 겹치는 관계니까 2 출력

(x2-x1)^2+(y2-y1)^2 가 더 크면 만나지 않는 관계니까 0 출력

추가로 (x1,y1)(x2,y2)가 같으면 같은 좌표에 위치했으니 r1 r2값이 다르면 서로 만나지 않고 r1 r2값이 같으면 같은 원이니 출력값을 -1로 지정하였다.

T=int(input())
for i in range(T):
  x1,y1,r1,x2,y2,r2=map(int,input().split())
  if x1==x2 and y1==y2:
    if r1==r2:
      print(-1)
    elif r1!=r2:
      print(0)
  else:
    if (x2-x1)**2+(y2-y1)**2<(r1+r2)**2:
      print(2)
    elif (x2-x1)**2+(y2-y1)**2==(r1+r2)**2:
      print(1)
    elif (x2-x1)**2+(y2-y1)**2>(r1+r2)**2:
      print(0)

하지만 위 코드로 제출을 하니 50%에서 틀렸습니다가 나와서

원인을 알아보니 내접원(원 안의 원이 위치한 경우)의 가능성을 고려하지 않았던 것이었다. 

 

그래서 고등학교 시절 배웠던 두 원사이의 위치관계에 대한 내용을 다시 찿아보니 쉽게 코드를 작성할 수 있었다.

출처: https://mathjk.tistory.com/178

 

T=int(input())
for i in range(T):
  x1,y1,r1,x2,y2,r2=map(int,input().split())
  d=((x2-x1)**2+(y2-y1)**2)**(1/2)
  if (r1+r2<d) or (abs(r1-r2)>d) or (d==0 and r1!=r2):
    print(0)
  elif (d==0 and r1==r2):
    print(-1)
  elif (r1+r2==d) or (abs(r1-r2)==d):
    print(1)
  elif (abs(r1-r2)<d) and (d<(r1+r2)):
    print(2)

 

실버 문제를 풀다보니

에라토스테네스의 체라던지 유클리드 호제법이라던지 수학적인 개념을 활용하는 알고리즘 문제가 점점 등장함을 알 수 있었다. 두 원 사이의 관계와 같은 수학적인 문제는 사전 지식없이 바로바로 생각해서 푸는 것은 불가능에 가깝다고 생각한다.(내가 수학자도 아니고) 따라서 문제에서 등장하는 수학 개념만이라도 익숙해지게 공부를 해야겠다.