[알고리즘] 백준 1002 터렛

알고리즘 분류

: 수학, 기하학, 많은 조건 분기

 

❓Question

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.
조규현의 좌표 (x1,y1)와 백승환의 좌표 (x2,y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

 

‼️ Answer

조규현의 좌표와 백승환의 좌표를 기준으로 각각 r1과 r2를 반지름으로 가진 원을 그려준다.

 

👉두 원이 만나는 점이 류재명이 있을 수 있는 위치이다.

     따라서 두 사람의 거리와, 두 개의 반지름의 값을 통해 두 원이 만나는 경우의 수를 나눈다. 

 

두 사람의 거리 

let d = Math.sqrt(Math.pow((x2-x1),2) + Math.pow((y2-y1),2));

두 원이 만나는 경우의 수

☝️ 두 원이 떨어져 있는 경우 (d > r1+r2)

=> 두 원이 만나지 않으므로 류재명이 존재할 수 없다. 

 

✌️두 원이 접한 경우 (d = r1+r2)

=> 두 원은 한 점에서 만나기 때문에 류재명이 존재할 수 있는 경우의 수는 1개이다. 

 

👌 두 원이 겹친 경우 (d < r1+r2)

두 원이 만나는 점이 2개이기 때문에 류재명이 존재할 수 있는 경우의 수는 2개이다. 

하지만 예외상황이 존재한다. 

 

1) 작은 원이 큰 원에 들어가서 접한 경우 (d = |r1-r2|)

=> 두 개의 원이 하나의 점에서 만나므로 류재명이 존재할 수 있는 위치는 1개이다. 

 

 

2) 작은 원이 큰 원에 들어가 접하지 않은 경우 (d < |r1-r2|)

=> 두 개의 원이 만나지 않으므로 류재명이 존재할 수 있는 위치는 없다.

🖐️두 원이 완전히 겹친 경우 

=> 두 원이 완전히 겹쳤으므로 류재명이 존재할 수 있는 위치는 무한 개이다. 

 

 

 

위의 몇 가지 경우의 수를 고려하여 if문을 통해 작성한 코드는 다음과 같다. 

let answer = [];
  let n = input.shift();

  input.forEach((val,idx) => {
    
    let [x1,y1,r1,x2,y2,r2] = val.split(' ').map(Number);
    let result = 0;

    let d = Math.sqrt(Math.pow((x2-x1),2) + Math.pow((y2-y1),2));

    if(x1 === x2 && y1 === y2 && r1 === r2) result = -1
    else if(d > r1+r2) result = 0
    else if (d === r1+r2) result = 1
    else if(d< r1+r2) {
      if(r1 >= r1 && d===r1-r2) result = 1
      else if(r1 < r2 && d===r2-r1) result = 1
      else if(r1 >= r2 && d<r1-r2) result = 0;
      else if(r1 < r2 && d<r2-r1) result = 0;
      else result = 2;
    }
    answer.push(result);
  })
  console.log(answer.join('\n'));

 

 

---

알고리즘 문제를 처음 풀 때는 큰 원이 작은 원에 들어가게 되는 예외상황을 고려하지 못해서 문제를 푸는 데 오래걸렸다. 

입출력 예시 부분에도 없어서 인터넷의 도움을 받았다...

그래도 문제에 접근하는 방법에 어느정도 가까워서 뿌듯했다. 다음에 비슷한 문제가 나오게 되면 예외상황을 빠뜨리는 상황이 없도록 블로그에 작성해보았다. 고등학교  때 접했던 두 원 사이의 거리 문제가 나와 반가웠지만 어려웠던 문제였당....