02 기초 수학과 구현 - 최장 맨해튼 거리

최장 맨해튼 거리

 

맨해튼 거리(Manhattan Distance)는 각 좌표의 차를 모두 더한 것을 거리로 한다.
즉, |x1−x2|+|y1−y2|가 두 점 (x1,y1), (x2,y2) 사이의 맨해튼 거리이다.

두 개의 정수를 임의로 짝을 지어 좌표로 나타냈을 때, 최장 맨해튼 거리를 구해보자

 

 

맨해튼 거리 구현

# 맨해튼 거리 공식
>>> def manhattan_distance(pt1, pt2):
>>>   distance = 0
>>>   for i in range(len(pt1)):
>>>     distance += abs(pt1[i] - pt2[i])
>>>   return distance

# 2차원에서 임의의 두점 (순서대로 x,y축)
>>> print(manhattan_distance([5, 8], [3,6])

# x, y, z축 3의 차원에 점을 나타내고 싶다면 ([5, 4, 3], [1, 7, 9])

 

 

 

근데 이제 여기서 문제는 2차원의 최장 거리를 나타내야 한다는 것인데,

모든 경우의 수 (4!=24 가지)를 다 따져봐야 한다 -  완전탐색을 이용

 

(코드로 구현하느니 24개를 손으로 해보겠다)

 

 

 

 

 

완전 탐색을 이용한 해설

 

>>> S = list(map(int, input().split()))

# 값을 0으로 초기화
>>> ans = 0

>>> for a in S:
>>>     x1 = a
>>>     for b in S:
        # 수를 중복해서 사용하면 안 된다!
>>>         if a == b:
>>>             continue
>>>         y1 = b
>>>         for c in S:
>>>             if a == c or b == c:
>>>                 continue
>>>             for d in S:
>>>                 if a == d or b == d or c == d:
>>>                     continue
>>>                 y2 = d
                # 맨해튼 거리 계산
>>>                 dist = abs(x1 - x2) + abs(y1 - y2)
                # 가장 큰 값으로 정답 갱신
>>>                 ans = max(ans, dist)

>>> print(ans)

 

 

 

수학적 접근

 

 

ㅣx1 - x2ㅣ+ ㅣy1 - y2ㅣ에서 절댓값 기호를 제거하자 -> x1 + y1 - x2 - y2

(절댓값 안이 항상 양수라고 가정)

 

 

입력받은 4개의 정수를 크기 순으로 정렬한 후 순서대로 a, b, c, d라고 할때,

더해지는 값은 클수록 이득이고 빼야하는 값은 작을수록 이득이다

 

 

a <  b < c < d 이므로,

x1, y1는 c, d (큰 값)

x2, y2는 a, b (작은 값) 이 된다

 

 

 

이걸 시험보면서 어케 생각하냐

 

 

 

 

따라서 이렇게 간단하게 정리가 가능하다

 

 

>>> S = list(map(int, input().split()))
>>> S.sort()
>>> print(S[3] + S[2] - S[1] - S[0])