C++에서 맨해튼 거리와 동일한 거리를 갖는 경로의 개수 구하는 방법

2차원 좌표평면 위의 두 점 (x1, y1)과 (x2, y2)가 주어졌을 때, 두 점 사이의 맨해튼 거리(Manhattan Distance)와 정확히 같은 거리를 갖는 모든 경로의 개수를 구하는 것이 목표입니다.

맨해튼 거리란?

두 점 (x1, y1)과 (x2, y2) 사이의 맨해튼 거리는 다음과 같이 정의됩니다.

MD = |x1 − x2| + |y1 − y2|

설명의 편의를 위해 A = |x1 − x2|, B = |y1 − y2|라고 하겠습니다.

맨해튼 거리와 같은 거리를 갖는 모든 경로는 A개의 수평 이동과 B개의 수직 이동, 즉 총 (A+B)개의 이동으로 구성됩니다. 따라서 가능한 경로의 개수는 (A+B)개의 이동을 수평 이동 그룹과 수직 이동 그룹, 두 그룹으로 나누는 조합의 수와 같으며, 다음 공식으로 계산할 수 있습니다.

(A+B)CB = (A+B)! / (A! × B!)

예시

입력: x1 = 6, y1 = 8, x2 = 2, y2 = 10

출력: 맨해튼 거리와 같은 거리를 갖는 경로의 개수: 15

설명:

A = |6 − 2| = 4
B = |8 − 10| = 2
(A+B)CB = 6C2 = 6! / (4! × 2!) = 720 / 48 = 15

구현 접근 방법

이 문제는 복잡한 탐색 없이 조합 공식만으로 간단하게 해결할 수 있습니다.

• 두 점의 x좌표 차이의 절댓값 A와 y좌표 차이의 절댓값 B를 구합니다.

• 전체 이동 횟수는 A+B이며, 그중 B번은 수직 이동입니다.

• 조합 공식 (A+B)CB를 적용하여 가능한 경로의 총 개수를 계산합니다.

• 팩토리얼 값이 빠르게 커지므로, 오버플로우를 방지하기 위해 곱셈과 나눗셈을 교차하며 이항계수를 단계적으로 계산합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
long long int bio_coeff(int A, int B){
    long long int temp = 1;
    if (B > A - B){
        B = A - B;
    }
    for (int i = 0; i < B; ++i){
        temp = temp * (A - i);
        temp = temp / (i + 1);
    }
    return temp;
}
long long int Manhattan_distance(int x1, int y1, int x2, int y2){
    int A = abs(x1 - x2);
    int B = abs(y1 - y2);
    int count = bio_coeff(A + B, B);
    return count;
}
int main(){
    int x1 = 6, y1 = 8, x2 = 2, y2 = 10;
    cout<<"Count of paths with distance equal to Manhattan distance are: "<<
    Manhattan_distance(x1, y1, x2, y2);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of paths with distance equal to Manhattan distance are: 15