문제
어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.
![](https://blog.kakaocdn.net/dn/bDsJ5K/btrGzcNze34/hGBqTi7QudFHCtBtOzigq0/img.gif)
빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.
위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다.
출력
각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.
제한
- -1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000
- 1 ≤ r ≤ 1000
- 1 ≤ n ≤ 50
- 좌표와 반지름은 모두 정수
예제 입력 1
2
-5 1 12 1
7
1 1 8
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2
-5 1 5 1
1
0 0 2
예제 출력 1
3
0
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');
const T = +input.shift();
const matrix = input.map((el) => {
return el.split(' ').map(Number);
});
function solution(T, matrix) {
for(let i=0; i<T; i++) {
const [x1, y1, x2, y2] = matrix.shift();
const n = matrix.shift();
let result = 0;
for(let j=0; j<n; j++) {
const [cx, cy, r] = matrix.shift();
let cnt = 0;
/* 거리 구하는 공식 : sqrt((x2 - x1)^2 + (y2 - y1)^2)*/
/* 루트를 씌워야 하므로 양변에 제곱을 해서 비교했다 */
// 출발점과 원의중심 사이의 거리가 반지름보다 작을 경우,
// 한마디로 출발점이 원의 내부에 있을 경우
if((x1 - cx)**2 + (y1 - cy)**2 < r**2) cnt++;
// 도착점과 원의중심 사이의 거리가 반지름보다 작을 경우,
// 한마디로 도착점이 원의 내부에 있을 경우
if((x2 - cx)**2 + (y2 - cy)**2 < r**2) cnt++;
// if(cnt === 0): 둘다 원의 내부에 있으므로 진입/이탈 x
if(cnt === 1) result++;
// if(cnt === 2): 둘다 원의 외부에 있으므로 진입/이탈 x
}
console.log(result);
}
}
solution(T, matrix);
'PS > 백준' 카테고리의 다른 글
백준 / 그래프 / 13549번 / 숨바꼭질 3 / JS (0) | 2022.07.29 |
---|---|
백준 / 그리디 / 1543번 / 문서 검색 / JS (0) | 2022.07.13 |
백준 / 기하학 / 1358번 / 하키 / JS (0) | 2022.07.05 |
백준 / Recursion(재귀) / 17478번 / 재귀함수가 뭔가요? / JS (0) | 2022.07.04 |