LGV Theorem (Lindstrom-Gessel-Viennot)

LGV Theorem, Lindstrom-Gessel-Viennot Lemma, LGV 보조정리

정의

Lindstrom-Gessel-Viennot (LGV) Theorem 은 DAG (또는 격자) 에서 N 개의 시작점 / N 개의 끝점이 주어졌을 때 교차하지 않는 (non-intersecting) 경로 시스템의 부호 합 = 행렬식 으로 표현된다는 정리.

A = [w(s_i -> t_j)]_{N x N}
det(A) = Σ_{σ ∈ S_N} sgn(σ) · Σ_{non-intersecting path systems s_i -> t_{σ(i)}} Π weights

격자에서 위 / 오른쪽 으로만 가는 경로 처럼 자연스럽게 교차하지 않는 매칭이 항등치환만 인 경우, 행렬식 = 단순 경로 카운팅.

문제 상황과 동기

격자 / DAG 위에서 N 개의 시작점에서 N 개의 끝점까지 서로 교차하지 않는 경로를 그리는 경우의 수 를 세는 문제.

naive approach: 모든 경로 조합 (지수 개) 을 나열하고 교차 여부 체크 → 불가능.

단순 곱셈 Π paths(s_i, t_i) 는 교차를 허용한 경우의 수. 교차하는 쌍을 inclusion-exclusion 으로 빼내는 것도 복잡도가 폭발한다.

핵심 인사이트: 행렬식 det(M) 의 정의 자체가 모든 치환 σ 의 부호 합 이다. 교차하는 경로 시스템 쌍은 swap (transposition) 으로 서로 상쇄 되고, 교차하지 않는 경로 시스템만 최종적으로 남는다 (involutive proof).

따라서 M[i][j] = paths(s_i, t_j) 행렬의 행렬식 = 교차 없는 경로 시스템 수. 행렬식 계산은 Gaussian elimination O(N³).

PS 에서는 “격자 위 N 개 로봇이 서로 지나치지 않고 목적지까지” 같은 문제가 LGV 로 단 몇 줄에 해결된다.

시각화

핵심 성질

1. non-intersecting path system 카운팅 = 행렬식 (항등치환 매칭만 가능할 때)
2. 일반 케이스는 signed sum 이지만 좋은 격자에서는 양의 답
3. 교차하는 path system 들이 swap 으로 쌍을 이루어 상쇄 (involutive proof)

격자 응용

가장 흔한 케이스: (0, 0) → (a, b) 의 격자 경로 수 = C(a + b, a). N 개의 시작 / 끝점이 위 / 오른쪽 으로만 가는 경로면:

M[i][j] = C( (t_j.x - s_i.x) + (t_j.y - s_i.y), t_j.x - s_i.x )
det(M) = non-intersecting path systems 수

구현

// O(N³) LGV Theorem for lattice paths (mod p)
// s[i] = (x_s[i], y_s[i]), t[j] = (x_t[j], y_t[j])
// 위/오른쪽 이동만 가능. M[i][j] = C(dx+dy, dx) 계산 후 행렬식
#include <vector>
using namespace std;

const long long MOD = 1e9 + 7;

long long modpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long modinv(long long x, long long mod) {
    return modpow(x, mod - 2, mod);
}

// 이항계수 전처리 (작은 범위 O(N²), 큰 범위는 Lucas / 다른 방법)
const int MAXN = 2005;
long long C[MAXN][MAXN];
void precompute_binomial() {
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

// Gaussian elimination 으로 행렬식 계산 (mod p)
long long det_mod(vector<vector<long long>> M, long long mod) {
    int n = M.size();
    long long det = 1;
    
    for (int col = 0; col < n; col++) {
        // pivot 찾기
        int pivot = -1;
        for (int row = col; row < n; row++) {
            if (M[row][col] % mod != 0) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) return 0; // singular
        
        if (pivot != col) {
            swap(M[col], M[pivot]);
            det = (mod - det) % mod; // 행 교환 → 부호 반전
        }
        
        long long pivot_val = M[col][col];
        det = det * pivot_val % mod;
        long long inv = modinv(pivot_val, mod);
        
        // 아래 행들을 0 으로
        for (int row = col + 1; row < n; row++) {
            long long factor = M[row][col] * inv % mod;
            for (int k = col; k < n; k++) {
                M[row][k] = (M[row][k] - factor * M[col][k] % mod + mod) % mod;
            }
        }
    }
    
    return det;
}

// LGV main: s[i] = (x_s, y_s), t[j] = (x_t, y_t)
long long lgv_lattice(vector<pair<int, int>> s, vector<pair<int, int>> t, long long mod) {
    int n = s.size();
    vector<vector<long long>> M(n, vector<long long>(n));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int dx = t[j].first - s[i].first;
            int dy = t[j].second - s[i].second;
            if (dx < 0 || dy < 0) {
                M[i][j] = 0; // 도달 불가
            } else {
                M[i][j] = C[dx + dy][dx];
            }
        }
    }
    
    return det_mod(M, mod);
}

예시 실행

입력:
s = [(0, 0), (0, 1)]
t = [(2, 2), (2, 3)]
(2명이 각각 (0,0) → (2,2), (0,1) → (2,3) 으로, 교차 없이)

M[0][0] = C(2+2, 2) = 6
M[0][1] = C(2+3, 2) = 10
M[1][0] = C(2+1, 2) = 3
M[1][1] = C(2+2, 2) = 6

det(M) = 6·6 - 10·3 = 36 - 30 = 6

답: 6 가지 교차 없는 경로 시스템

응용

1. Intersection is Not Allowed!

격자 위에서 N 명이 시작점에서 끝점까지 서로 교차하지 않는 경로 수.

2. Ascending Matrix

격자 / 부분 순서 위 단조 매트릭스 카운팅.

3. Schur Polynomial 계수

대수 응용.

4. Domino Tiling

특정 형태의 영역 도미노 타일링 = LGV.

복잡도

작업	비용
매트릭스 구성	O(N²)
행렬식 (Gaussian elimination)	O(N³)
Big modular determinant	O(N³ log p)

PS 에서는 N ≤ 1000 까지 안정적.

함정

1. 항등치환 매칭만 가능한지

각 (s_i, t_j) 페어가 교차 없이 도달 가능한 매칭이 항등치환뿐인 배치 여야 단순 카운팅. 그렇지 않으면 signed sum 이 양 / 음 / 0 으로 나옴.

2. mod p 행렬식

큰 p (10^9+7) 에서 Gaussian elimination + modular inverse. 또는 Bareiss 알고리즘 (정수 / mod 일반화).

3. 격자 외 일반 DAG

DAG 에서도 weight 가 잘 정의되면 적용 가능. 다만 weight 계산이 비자명.

4. degeneracy

두 경로가 겹치는 점 (단순 교차 아님) 을 어떻게 처리할지 정의를 명확히. 정의에 따라 결과가 달라짐.

BOJ 연습 문제

번호	제목	링크
BOJ 19514	Intersection is Not Allowed!	kokoa-lab
BOJ 21265	Ascending Matrix	kokoa-lab

참고

• Young Tableau (LGV 의 표현론 응용)
• Generating Function
• Matroid