[백준] 3053번 - 택시 기하학 (Java)

문제

https://www.acmicpc.net/problem/3053

3053번: 택시 기하학

 

풀이

2가지 '두 점 사이의 거리' 정의를 이용해 원의 넓이를 각각 구하는 문제이다. 유클리드 기하학, 택시 기하학(맨헤튼 거리) 두 가지 기하학에서 '두 점 사이의 거리'에 대해 다르게 정의하고 있다.

• [유클리드] D(T₁, T₂)² = (𝑥₁ - 𝑥₂)² + (y₁ - y₂)²
• [택시] D(T₁, T₂) = |𝑥₁ - 𝑥₂| + |y₁ - y₂| 

그러나, 두 기하학에서 '두 점 사이의 거리'에 대한 정의는 다르지만 원의 정의는 같다.

• [유클리드 / 택시] 원: 평면 상의 어떤 점에서 거리(반지름)가 일정한 점들의 집합

원의 넓이를 구하기 위해서는 반지름이 필요한데, 반지름 또한 '두 점 사이의 거리' 에 해당한다. 그러나, 앞서 얘기했듯 두 점 사이의 거리를 판단하는 기준이 다르기 때문에 같은 반지름 값으로 원을 그리려 해도 유클리드 기하학과 택시 기하학에서의 원의 모양이 달라지게 된다.

 

반지름 3의 원을 기준으로, 각 기하학 관점에서 길이 3의 직선(=두 점 사이의 거리)이 어떻게 그려지는지 확인해보자.

유클리드 기하학에서 거리 3	택시 기하학에서 거리 3

택시 기하학 쪽은 x, y좌표의 절대값을 이용하기 때문에 격자 단위로 길이를 측정한다고 보면 쉬울 것이다. 이러한 택시 기하학에서의 거리로 원을 그리게 되면 중심(0, 0)에서 같은 거리를 가진 점들의 집합으로 주변을 둘러싸야 하고 그 결과 정사각형 모양의 '원'이 그려진다. 모양은 절대 원이 아니지만, 기하학에서 정의한 '원'의 정의에 부합하기 때문에 이를 원이라고 부른다.

 

이번에는 좌표상으론 똑같은 위치의 두 점 A(0, 0), B(2, 1)로 두 점 사이의 거리를 계산해보자.

유클리드 기하학에서 거리	택시 기하학에서 거리
D(A₁, B₂)² = (𝑥₁ - 𝑥₂)² + (y₁ - y₂)² = (-2)² + (-1)² = 4 + 1 = 5 ∴ 두 점 A, B 사이의 거리 = √5	D(A₁, B₂) = |𝑥₁ - 𝑥₂| + |y₁ - y₂|  = |0-2| + |0-1| = 2 + 1 = 3 ∴ 두 점 A, B 사이의 거리 = 3

같은 위치의 두 점이 주어져도 각 기하학에서 구해지는 두 점 사이의 거리 값이 다르다. '두 점 사이의 거리'에 대한 정의가 다르면("두 점 사이의 거리란 ~을 일컷는다!") 이를 구하는 공식도 다르기 때문이다.

이제까지 이해한 것을 토대로 유클리드 기하학, 택시 기하학에서의 원의 넓이를 구해보면 아래와 같다.

• [유클리드] 원주율 x 반지름 x 반지름 = 𝜋𝑟² 
• [택시] 2 x 반지름 x 반지름 = 2𝑟²

 

택시 기하학의 경우에는 정사각형 넓이를 구하기 위해 1사분면에서의 삼각형 빗변 길이(빨간선)를 구해야 하는데, (=1사분면 직각삼각형의 빗변 길이임과 동시에 전체 정사각형 한 변의 길이) 이때, 피타고라스 정리를 활용해 반지름 길이(파란선)로 부터 이 빗변의 길이가 √2𝑟²라는 걸 구할 수 있다. 정사각형의 넓이 공식이 [가로 x 세로] 이기 때문에 √2𝑟² x √2𝑟² 로 2𝑟²가 된다.

• 정사각형 넓이 : 가로 x 세로
• 피타고라스 정리 : 직각삼각형의 빗변의 제곱이 두 직각 변의 제곱의 합과 같다.

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();           // 반지름 : 두 점 사이의 거리

        System.out.printf("%f\n", Math.PI * r * r);
        System.out.printf("%f", 2.0 * r * r);
    }
}

 

• 원주율(3.141593...) 값은 Math 클래스에 정의된 PI 상수(Math.PI)를 사용한다.

public static final double PI = 3.14159265358979323846;

• 소수점 아래 6자리 까지 출력하기 위해 printf() 메서드로 포맷팅해서 출력해야 한다. 별도로 자릿수를 지정하지 않을 시 기본적으로 소수점 아래 6자리까지 출력한다. (실수 값이 x.0 일 경우 x.000000으로 출력)

 

---

코드 자체는 엄청 짧고 간단했지만, 택시 기하학이라는 개념 자체를 몰라서 많이 헤맨 문제였다. 택시 기하학을 이해하는 과정에서도 두 기하학에서 원의 모양이 왜 다른가?에 대해서 납득하는데 많은 시간이 걸렸다. 수학 알고리즘을 풀기 위해서는 빈출 개념들을 미리 숙지해두는 게 시간면에서 중요하다는 것을 실감할 수 있었다.. 나중에 한번 제대로 총정리를 해야할듯

<수학 알고리즘 빈출 개념>

• 배수, 양수
• 최소공배수, 최대공약수
• 소수
• 에라토스테네스의 체
• 소인수분해
• 피타고라스 정리
• 두 점 사이의 거리
• 직각삼각형, 정사각형의 넓이
• 원의 넓이
• 각종 수학자들의 개념, 정리 등