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

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

3053번: 택시 기하학

 

---

• 문제

 

 

 

 

맨해튼 거리(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 _ ) 이다.

무슨 말인고 하니..

 

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

 

Primitive Type	Wraaper Class
byte	Byte
short	Short
int	Int
long	Long
float	Float
double	Double
boolean	Boolean
char	Character

 

 

 

즉 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 가 빠른 걸 볼 수 있다.

---

• 정리

 

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

 

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

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