[백준] 3053번 : 택시 기하학 - JAVA [자바]

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

 

3053번: 택시 기하학

문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |

www.acmicpc.net

 

---

• 문제

 

 

 

 

맨해튼 거리(Manhattan distance) 에 대해 알지 못한다면 이게 뭔 말이지 싶을 것이다.

(필자도 배웠던 기억이 있었으나 하도 오래전에 배운 내용이라 거의 까먹어서 다시 정의를 찾아보았다..)

 

참고로 택시 기하학은 맨해튼 거리의 다른 말이다.

 

 

그럼 택시 기하학을 한 번 알아보자. (매우 쉽다)

 

---

• 택시 기하학 (맨해튼 거리 , Manhattan distance)

 

사실 앞서도 잠깐 말했지만 정식적으로 쓰이는 말은 맨해튼 거리가 가장 대중적으로 쓰인다.

일단 문제에서 택시 기하학이라 했으니 이 단어로 설명하겠다.

 

 

일단 택시 기하학이 무엇인지 한 번 확인해보자.

 

위키백과에서는 아래와 같이 설명하고 있다.

 

 

 

 

우리가 자세히 볼 것은 오른쪽 위의 그림이다.

 

문제에서 택시 기하학에서의 거리는 아래와 같다고 했다.

D(T₁, T₂) = |𝑥₁ - 𝑥₂| + |y₁ - y₂|

 

 

 

이 그림의 설명에서 볼 수 있듯이

빨간색, 파란색, 노란색의 선의 길이는 모두 같다.

 

이 것이 포인트다.

 

즉 2차원 평면에서 가로를 x, 세로를 y 라고 할 때,

택시 기하학에서의 거리 = 두 점의 x 좌표의 차 + 두 점의 y 좌표의 차 가 되는 것이다.

 

 

 

우리가 평소에 아는 '거리' 라는 개념은 초록색(유클리드 기하학)과 같지만 ( D(T₁, T₂)² = (𝑥₁ - 𝑥₂)² + (y₁ - y₂)² )

택시기하학에서는 '거리'라는 개념을 새로 정의한 것이다. ( D(T₁, T₂) = |𝑥₁ - 𝑥₂| + |y₁ - y₂| )

 

 

 

 

 

 

그러면 거리라는 것을 알았으니, 문제에서 요구하는 유클리드 기하학에서 원의 넓이와 택시 기하학에서 원의 넓이를 생각해보자.

 

거리 r (반지름) 이 3 으로 주어졌을 때를 가정해보자.

 

일반적으로 거리가 3인 좌표들을 그림으로 그려보면 원이 나온다.

 

 

 

 

그러면 해당 원의 넓이는 아래와 같다.

 

원의 넓이 = 𝜋𝑟² 

               = 3 × 3 × 𝜋 

               = 9𝜋

 

 

 

 

그렇다면 택시기하학에서 재정의한 거리를 좌표상으로 표현하면 어떻게 그려질까?

 

아까 위키백과에서 맨해튼 거리의 원에 대해 다음과 같이 설명하고 있다.

 

 

 

이 글의 포인트는

"맨해튼 거리의 원은 중심 점에서 반지름이라고 불리는 일정한 거리만큼 떨어져 있는 점들의 집합이다" 이다.

 

즉 우리가 택시기하학에서의 거리에 대한 정의인 D(T₁, T₂) = |𝑥₁ - 𝑥₂| + |y₁ - y₂| 에서 D 는 거리였다.

이 D 를 반지름이라고 볼 때 위 공식을 단순화 하면 아래와 같아진다.

 

D = |𝑥| + |y|

 

즉, 좌표상으로 D = |𝑥| + |y| 을 그리면, 아래와 같다.

( 거리 D = 3 )

 

 

 

위와같이 택시 기하학에서의 원은 정사각형이 45° 기울어진 모양이다.

 

 

그러면 택시기하학에서의 원의 넓이는 아래와 같다.

 

원의 넓이 = 2𝑟² 

               = 2 × 3 × 3 

               = 18 

 

 

 

 

그럼 정리해보자.

 

유클리드 기하학에서 반지름 𝑟 (거리) 이 주어졌을 때 원의 넓이는 아래와 같다.

   유클리드 기하학에서의 원의 넓이 = 𝜋𝑟² 

 

 

그리고 택시기하학에서 반지름 𝑟 (거리) 이 주어졌을 때 원의 넓이는 아래와 같다.

  택시 기하학에서의 원의 넓이 = 2𝑟² 

 

 

 

즉 문제에서 반지름(거리) 𝑟 을 입력받으면 위 두 공식에 대입하여 출력하면 끝난다.

 

 

---

• 2가지 방법을 이용하여 풀이한다.

 

 

입력을 달리하여 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		double R = in.nextDouble();	// 반지름 R
		in.close();
		
		System.out.println(R * R * Math.PI);	// 유클리드 원의 넓이
		System.out.println(2 * R * R);		// 택시기하학 원의 넓이
	}
}

 

 

앞서 공식은 모두 설명했으므로 크게 설명할 것은 따로 없다.

 

다만 출력시 오차 범위가 0.0001 이므로 double 형으로 사용하고, 𝜋 값은 Math.PI 를 쓰도록 하자.

참고로 자바 13 에서 Math.PI 가 정의된 값은 아래와 같다.

 

public static final double PI = 3.14159265358979323846;

 

 

 

---

- 방법 2 

 

 

Scanner 대신에 BufferedReader 로 입력받는 방법이다.

 

알고리즘 자체는 크게 다른 것이 없으니 형 변환만 조심해서 다루면 된다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
 
public class Main {
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		double R = Double.parseDouble(br.readLine()); // 반지름 R
	
		System.out.println(R * R * Math.PI);	// 유클리드 원의 넓이
		System.out.println(2 * R * R);		// 택시기하학 원의 넓이
		
	}
}

 

 

참고로 String 에서 기본 자료형, 즉 Primitive Type 으로 변환하는 방법은 아주 간단하다.

 

대응 Wrapper.parseWrapper(String _ ) 이다.

무슨 말인고 하니..

 

자바에서 기본 자료형의 데이터 타입과 이에 대응되는 래퍼클래스는 아래와 같다.

 

 

 

 

즉 String 을 byte 로 타입을 변환시키고 싶다면 Byte.parseByte(String _ ) 을 해주면 된다는 것이다.

 

참고로 char 은 문자의 연결된 형태가 문자열, 즉 char 이기 때문에 String 에서 char 로 변경하는 것은 없고, charAt() 메소드를 사용하면 된다.

 

타입별로 변환 방법은 아래와 같다.

 

String s1 = "123456";
 
byte a = Byte.parseByte(s1);		// String -> byte
short b = Short.parseShort(s1);		// String -> short
int c = Integer.parseInt(s1);		// String -> int
long d = Long.parseLong(s1);		// String -> long
float e = Float.parseFloat(s1);		// String -> float
double f = Double.parseDouble(s1);	// String -> double
 
String s2 = "true";
 
boolean g = Boolean.parseBoolean(s2);	// String -> boolean
 
// char 은 없음

 

 

 

 

 

 

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 19591855  -  BufferedReader

채점 번호 : 19591852  -  Scanner

 

 

입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이번 문제는 택시 기하학, 다른 말로 맨해튼 거리의 개념에 대해 알아보았다.

 

사실 맨해튼 거리가 지금 이 걸 왜 배우는 거지? 싶겠지만 나중에 심도있게 배우게 되다 보면 유사도라는 개념을 접하게 될 것이다.

이 유사도라는 개념이 바로 거리의 개념을 쓰게 되는데 꽤나 자주나오는 것 중 하나가 맨해튼 거리라 기회가 되면 포스팅해보도록 하겠다.