수학적 사고를 기반으로 복잡한 경로 문제를 푸는 것은 알고리즘 설계에 있어 매우 중요한 테크닉이다. 오늘은 특히 제한된 격자(Grid) 내에서 특정 구역을 피해야 할 때, 경로의 수를 빠르고 정확하게 계산하는 방법에 대해 다룬다. 이는 단순한 BFS나 DFS 접근으로는 절대 풀 수 없는 문제 규모를 가진다. 효율적인 수학적 공식 적용이 필수적이다.
문제 상황
Iroha는 크기가 H×WH \times W인 격자에서 좌상단 (0,0)에서 시작하여 우하단 (H-1, W-1)까지 이동해야 한다. 이동은 오직 오른쪽과 아래쪽으로만 가능하다. 그러나, 격자의 좌측 아래 AA행과 BB열이 겹치는 구역은 출입이 금지되어 있다. 이 문제에서 요구하는 것은 이 제약을 지키면서 도착점에 도달할 수 있는 경로의 수를 구하는 것이다.
조건은 다음과 같다.
- 1≤H,W≤100,0001 \leq H, W \leq 100,000
- 1≤A<H1 \leq A < H
- 1≤B<W1 \leq B < W
제약이 크기 때문에 모든 경로를 직접 탐색하는 방식은 사용할 수 없다. 반드시 수학적 방법, 특히 조합론(Combinatorics)을 이용해야 한다.
기본 접근: 조합을 통한 경로 계산
격자에서 단순히 오른쪽(Right)과 아래(Down)로만 이동할 수 있다면, (H-1)번 아래로, (W-1)번 오른쪽으로 이동해야 하므로 총 이동 횟수는 H+W−2H+W-2번이며, 그중 H−1H-1번을 아래로 이동하는 경우를 선택하는 문제로 볼 수 있다. 이는 조합으로 표현된다. Total Paths=C(H+W−2,H−1)\text{Total Paths} = C(H+W-2, H-1)
여기서 C(n,k)C(n, k)는 조합, 즉 C(n,k)=n!k!(n−k)!C(n, k) = \frac{n!}{k!(n-k)!}
를 의미한다.
하지만 이 문제는 단순히 전체 경로를 구하는 것이 아니라, 특정 구역(금지구역)을 반드시 피해야 한다는 조건이 추가된다.
금지구역을 피하기 위한 전략
금지구역은 격자의 하단 AA줄과 좌측 BB칸이 겹치는 A×BA \times B 구역이다. 이 구역에 진입하는 경로는 모두 무효로 간주된다.
이 문제를 해결하기 위해 두 구간으로 나눈다.
- (0,0) → (H-A+i, B-1): 금지 구역에 닿기 직전까지
- (H-A+i, B) → (H-1, W-1): 금지 구역을 건너뛰고 최종 목적지까지
여기서 ii는 금지구역과 경계지어지는 행을 따라 변화하는 값이다.
이 두 경로를 연결하여 합산해야 하므로, 각각의 경로의 수를 조합으로 계산한 뒤 곱하고, 다시 모든 가능한 ii에 대해 합산한다.
모듈러 연산의 필요성
입력의 최대 크기가 100,000이기 때문에, 조합을 계산할 때 수가 폭발적으로 커진다. 따라서 계산 과정에서 모든 결과는 109+710^9+7로 나눈 나머지(Modulo)를 취해야 한다.
이를 위해 사전 처리(preprocessing)로 팩토리얼(factorial)과 그 역원(inverse factorial)을 미리 계산해두는 방식이 사용된다. 이 경우 조합 계산을 O(1)O(1)에 할 수 있어 시간 초과를 방지할 수 있다.
모듈러 연산을 위한 기본 아이디어는 페르마의 소정리(Fermat’s Little Theorem)를 이용한 것이다. 소수 pp에 대해 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}
이므로, a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod{p}
를 이용해 역원을 빠르게 계산할 수 있다.
최적화된 구현 방법
아래는 이를 구현한 최적화된 방식의 요약이다.
- 팩토리얼 및 팩토리얼 역원 미리 계산
- 시간복잡도: O(H+W)O(H+W)
- 조합 계산은 O(1)O(1)
- 모든 가능한 ii에 대해 경로를 합산
결국, 전체 코드는 효율적으로 작성되며, 주어진 시간 안에 문제를 해결할 수 있게 된다.
실제 코드 흐름
- 팩토리얼과 역팩토리얼 배열 준비
- (0,0) → (H-A+i, B-1)까지의 경로 수 계산
- (H-A+i, B) → (H-1, W-1)까지의 경로 수 계산
- 두 경로를 곱해 모듈러 연산한 후 누적 합
- 최종 결과 출력
결론
이 문제는 겉으로 보면 단순한 경로 수 계산처럼 보이지만, 제한 조건이 추가되면서 수학적 사고와 최적화 기술을 동시에 요구한다. 단순 구현이 아니라, 조합론, 모듈러 연산, 사전 처리 전략을 적절히 활용해야 한다. 이러한 접근 방식을 익히고 연습해두는 것은 고난이도 알고리즘 문제를 풀 때 큰 무기가 된다. 이처럼 격자 문제에서도 수학과 컴퓨터 과학의 긴밀한 결합을 체감할 수 있다.
답글 남기기