C++로 그리드에서 한 지점에서 다른 지점까지 이동하는 경로의 수 구하기

이 글에서는 그리드(grid) 위의 한 지점 A에서 다른 지점 B까지 이동할 수 있는 총 경로의 수를 구하는 문제를 다룹니다. 여기서 A는 그리드의 왼쪽 위 꼭짓점, B는 오른쪽 아래 꼭짓점으로 고정되어 있습니다.

입력 : N = 5
출력 : 252

입력 : N = 4
출력 : 70

입력 : N = 3
출력 : 20

주어진 문제는 간단한 관찰만으로도 답을 공식화할 수 있으며, 이를 통해 빠르게 결과를 얻을 수 있습니다.

문제 해결 접근 방법

이 접근 방식은 간단한 관찰을 바탕으로 문제의 답을 하나의 공식으로 만듭니다. 그리드에서 A 지점에서 B 지점으로 이동하려면 오른쪽 방향으로 정확히 n번, 아래쪽 방향으로 정확히 n번, 즉 총 2n번의 이동이 필요합니다. 따라서 전체 2n번의 이동 중에서 오른쪽(또는 아래쪽)으로 갈 n번의 순서를 선택하는 모든 경우의 수를 구하면 되며, 이는 조합 공식 C(2n, n) = (2n)! / (n! × n!)으로 표현됩니다.

예제 코드

#include<bits/stdc++.h>

using namespace std;
int fact(int n){ // 팩토리얼 함수 
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int main() {
   int n = 5; // 주어진 n
   int answer = 0; // 구하고자 하는 답
   answer = fact(n+n); // 2*n의 팩토리얼 계산
   answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! × n!)
   cout << answer << "\n";
}

실행 결과

252

코드 설명

위 코드에서는 2nCn 조합 공식을 계산합니다. A 지점에서 B 지점으로 이동하려면 두 방향으로 정확히 2n번의 이동이 필요합니다. 즉, 한 방향으로 n번, 다른 방향으로 n번 이동해야 하므로, 이 이동들의 가능한 모든 조합의 수인 (2n)! / (n! × n!)을 구하면 됩니다.

이 방식은 동적 계획법(DP)으로 격자 칸마다 경로 수를 채워 나가는 O(N²) 방식과 달리, 하나의 공식만으로 곧바로 답을 계산하기 때문에 매우 효율적입니다. 다만 팩토리얼 값이 매우 빠르게 커지므로, n이 커질 경우 오버플로우를 방지하기 위해 long long 타입 사용이나 모듈러 연산 적용을 고려하는 것이 좋습니다.

결론

이 글에서는 그리드에서 한 지점에서 다른 지점으로 이동하는 경로의 수를 구하는 문제를 살펴보았습니다. 조합 공식을 활용한 해결 아이디어와 함께 이를 구현한 C++ 프로그램 및 전체적인 접근 방법을 학습했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.