𝝅번째 알파카의 개발 낙서장

screen

[백준 / JAVA] 백준 알고리즘 1002번 터렛

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

터렛 🔗

랭크 사용 언어
image JAVA

🔗 전체 1002번 문제

조건 🔗

시간제한 메모리 제한
2초 128MB

문제 🔗

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

image

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

입력 🔗

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
한 줄에 , , , , , 가 주어진다. , , , 는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 점수이고, , 는 10,000보다 작거나 같은 자연수이다.

출력 🔗

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

케이스 🔗

  • 입력

TC

03
10 0 13 40 0 37
20 0 30 0 7 4
31 1 1 1 1 5
  • 출력

TC

02
11
20

풀이 🔗

예제의 요소를 사람 이름으로 두었으나, 문제 이해에 방해가 되니 간단하게 서술하면 아래와 같다.
임의의 위치에 있는 점 , , 가 존재하며, 의 거리, 의 거리가 주어진다.
이 때, 가 실제로 위치할 수 있는 점의 갯수를 구하는 것. 즉, 간단하게 두 원의 접점을 구하는 문제라고 정의할 수 있다.
원이 완벽하게 겹칠 경우, 그 수가 무수히 많으므로 -1로 표현하라는 조건이 포함된다.

이를 그림으로 표현하면 아래와 같다.

image

변수는 아래와 같이 정리할 수 있다.

1 A의 x좌표 A의 y좌표 A의 반지름
2 B의 x좌표 B의 y좌표 B의 반지름

케이스를 세분화하면 총 6가지로 나눌 수 있다.

  1. 두 원이 정확히 겹칠 경우 (-1)
  2. 두 원이 서로 겹치면서 인접하지 않는 경우 (0)
  3. 두 원이 서로 겹치지 않으면서 인접하지 않는 경우 (0)
  4. 두 원이 서로 겹치면서 인접하는 경우 (1)
  5. 두 원이 서로 겹치지 않으면서 인접하는 경우 (1)
  6. 두 원이 서로 겹치면서 인접하지 않는 경우 (2)

본 풀이에선 , , 의 거리() 및 , 를 합한 길이()와 뺀 길이()의 절대값을 이용하여 진행한다.

  • case 1 - 두 원이 정확히 겹칠 경우

    두 원의 위치 및 반지름이 서로 동일한 상황.
    가 0이며, 의 길이가 동일할 경우 성립한다.

  • case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우

    두 원의 원점과의 거리가 반지름의 차이보다 짧은 상황.
    일 경우 성립한다.

  • case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우

    두 원의 원점과의 거리가 반지름의 합보다 긴 상황.
    일 경우 성립한다.

  • case 4 - 두 원이 서로 겹치면서 인접하는 경우

    두 원의 원점과의 거리가 반지름의 차이와 일치하는 상황.
    일 경우 성립한다.

  • case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우

    두 원의 원점과의 거리가 반지름의 합과 일치하는 상황.
    일 경우 성립한다.

  • case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우

    두 원이 서로 적당히 겹치는 상황.
    일 경우 성립한다.

굳이 식으로 표현하지 않아도, 위의 5개 케이스에 부합하지 않는 모든 상황에 적용하면 된다.
위 케이스들을 if문을 사용하여 적절히 표현하면 된다. switch문의 경우 하나의 변수를 기준으로 분기를 판단하므로 해당 알고리즘에 적용하기엔 다소 부적절하다.

전체 소스 🔗

JAVA

0import java.util.Scanner;
1
2/**
3 * 백준 전체 1002 문제 알고리즘 클래스
4 *
5 * @author RWB
6 * @see <a href="https://blog.itcode.dev/posts/2021/05/21/a1002">1002 풀이</a>
7 * @since 2021.04.21 Wed 21:56:10
8 */
9public class Main
10{
11 /**
12 * 메인 함수
13 *
14 * @param args: [String[]] 매개변수
15 */
16 public static void main(String[] args)
17 {
18 Scanner scanner = new Scanner(System.in);
19
20 int length = scanner.nextInt();
21
22 for (int i = 0; i < length; i++)
23 {
24 int x1 = scanner.nextInt();
25 int y1 = scanner.nextInt();
26 int r1 = scanner.nextInt();
27
28 int x2 = scanner.nextInt();
29 int y2 = scanner.nextInt();
30 int r2 = scanner.nextInt();
31
32 System.out.println(calcPoints(x1, y1, r1, x2, y2, r2));
33 }
34 }
35
36 /**
37 * 접점 갯수 반환 함수
38 *
39 * case 1 - 두 원이 정확히 겹칠 경우 (-1)
40 * case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우 (0)
41 * case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우 (0)
42 * case 4 - 두 원이 서로 겹치면서 인접하는 경우 (1)
43 * case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우 (1)
44 * case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우 (2)
45 *
46 * @param x1: [int] A의 x좌표
47 * @param y1: [int] A의 y좌표
48 * @param r1: [int] A와 C 사이의 거리
49 * @param x2: [int] B의 x좌표
50 * @param y2: [int] B의 y좌표
51 * @param r2: [int] B와 C 사이의 거리
52 *
53 * @return [int] 접점 갯수
54 */
55 private static int calcPoints(int x1, int y1, int r1, int x2, int y2, int r2)
56 {
57 // 두 점 사이의 거리 계산식
58 double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
59
60 int sum = r1 + r2;
61 int sub = Math.abs(r1 - r2);
62
63 // case 1 - 두 원이 정확히 겹칠 경우
64 if (distance == 0 && r1 == r2)
65 {
66 return -1;
67 }
68
69 // case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우
70 else if (distance < sub)
71 {
72 return 0;
73 }
74
75 // case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우
76 else if (distance > sum)
77 {
78 return 0;
79 }
80
81 // case 4 - 두 원이 서로 겹치면서 인접하는 경우
82 else if (distance == sub)
83 {
84 return 1;
85 }
86
87 // case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우
88 else if (distance == sum)
89 {
90 return 1;
91 }
92
93 // case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우
94 else
95 {
96 return 2;
97 }
98 }
99}

분류 🔗

  • 수학
  • 기하학