015. Lattice Paths (격자에서 원점에서 마지막점까지의 경로에 대한 경우의 수 구하기)

​문제 (English)

Starting in the top left corner of a $2 \times 2$grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many search routes are there through $20 \times 20$ grid?

 

Answer: 137846528820

문제 분석

---

Grid에 대해 (0,0) 포인트의 시작점에서 시작해서 (m,n) 지점까지 가는 경우의 수를 구하는 문제이다. 이동할 때는 가로로는 오른쪽으로, 세로로는 아래쪽으로 이동하면서.

 

다이내믹 프로그래밍으로 풀 수 있을 거다.

가로를 $x$축으로, 세로를 $y$로 놓고, 오른 방향을 $x$가 증가하는, 아랫 방향을 $y$가 증가하는 방향으로 놓고서, 각 지점에서의 이동할 수 있는 경우의 수를 C(x, y)로 놓고 풀면 되는.

 

또는, 이처럼 실제 Grid상의 지점을 이동하면서 경우의 수를 구하는 것이 아니라, 조합(Combination) 문제로 두고 풀 수도 있겠다.

 

풀이 1 

---

다이내믹으로 풀어본다.

 

가로를 $x$축, 세로를 $y$로 놓자. 오른 방향이 $x$증가 방향, 아랫 방향이 $y$증가 방향

p(1,1)로 올 수 있는 방법은 p(1,0)과 p(0,1)에서 오는 방법뿐. 

따라서, p(1,1)로 올 수 있는 경우의 수를 C(1,1)이라고 한다면, $C(1,1) = C(1,0) + C(0,1)$

 

일반화하면 $C(x,y) = C(x-1,y) + C(x, y-1)$

 

 

$C(1,1) = C(0,1) + C(1,0)$에서 C(0,1)과 C(1,0)의 값은 얼마일까?

$x=0$인 모든 점과 $y=0$인 모든 점에서의 C 값은 1이다.

 

p(2,0)으로 올 수 있는 경우의 수를 보면 $(0,0) \rightarrow (1,0) \rightarrow (2,0)$ 밖에  없기에 경우의 수는 1이다. 

fn answer1(n:i32, m:i32) -> u64{
    let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
    
    for i in 0..=n as usize { g[i][0] = 1;}
    for j in 0..=m as usize { g[0][j] = 1;}

    for i in 1..=n as usize {
        for j in 1..=m as usize{
            // g[i][j] = g[i-1][j] + g[i][j-1];
            g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
        }
    }
    return g[n as usize][m as usize];
}

 

위 코드에서 1000000007로 나머지 연산을 했다. 이것은 hackerrank 사이트에서 이 수로 나머지 연산을 한 값을 요구하기 때문. euler project 사이트에서는 $20 \times 20$의 문제만을 요구하기에 u64로도 처리할 수 있는데, hackerrank에서는 $500 \times 500$ 문제까지 요구하고, 이 답은 매우 큰 수이기에 1000000007로 나눈 나머지만 답으로 출력하라고 되어 있다.

 

hackerrank에서 동작되는 코드는 아래와 같다.

use std::io::{self, BufRead};

fn main(){
    let stdin = io::stdin();
    let mut it = stdin.lock().lines();
    
    let t = it.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
    for _ in 0..t {
        let v:Vec<String> = it.next().unwrap().unwrap().trim().split(' ')
                .map(|s| s.to_string()).collect();
        let n = v[0].trim().parse::<i32>().unwrap();
        let m = v[1].trim().parse::<i32>().unwrap();
        println!("{}", answer1(n,m));
    }
}

fn answer1(n:i32, m:i32) -> u64{
    let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
    
    for i in 0..=n as usize { g[i][0] = 1;}
    for j in 0..=m as usize { g[0][j] = 1;}

    for i in 1..=n as usize {
        for j in 1..=m as usize{
            // g[i][j] = g[i-1][j] + g[i][j-1];
            g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
        }
    }
    return g[n as usize][m as usize];
}

 

풀이 2 

---

이 문제를 다이내믹이 아닌, 조합 공식에 의해 풀 수도 있다.

 

(0,0)에서 시작해서 (m, n)까지로의 경로를 생각해 보면, 어떤 경로를 택하더라도 x 축으로 m번 움직이고, y축으로 n번 움직이는 것은 변함이 없다.

 

$5 \times 5$ 격자에 대해 생각해 보자.

 

1번 경로를 표시해 보면 $(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)$. $x$가 5번 나왔고, $y$가 5번 나왔다.

2번 경로를 표시해보면 $(y1,y2,y3,x1,y4,x2,y5,x3,x4,x5)$. 역시 5번씩 나왔다.

 

즉, $x1$에서 $x5$까지 5개와, $y1$에서 $y5$까지 5개. 총 10개에 대해서 순서를 세우는 문제이다.

 

문제를 단순화하기 위해서 $x$축에 대해서만 생각해 보면, 총 10개의 자릿수에 대해서 5개의 $x$가 위치할 자리를 결정하는 문제이다. 이때 $y$는 생각할 필요가 없다. $x$가 결정되면 나머지 자리에 들어가는 y는 고려할 필요가 없다. 

 

따라서, 이 문제는 조합(Combination) 문제이다. 

n개에서 k의 조합 공식은 $C(n,k) = \frac {n!} {k!(n-k)!}$

 

따라서 $5 x 5$ 격자에 대한 경로수는 $C(10,5) = \frac {10!}{5!5!} = 252$

 

---

$m \times n$ 격자에 대해서 일반화해보자. 

$C(m+n, m)$이 답이다. 이때 $C(m+n,n)$을 구해도 된다. 왜나면 둘 다 같은 값이기 때문

 

$C(m+n, m)$을 어떻게 구현할지 고민해 보자.

$C(m+n, m) = \frac {(m+n)!}{m!(m+n-m)!} = \frac {(m+n)!}{m!n!}$

여기서 $m>=n$ 이라고 한다면, 

$\frac {(m+n)!}{m!n!} = \frac {(m+n)(m+n-1)...(n+1}{n!} = \frac {(n+1)(n+2)...(m+n-1)(m+n)}{(1)(2)...(n)} = \frac{n+1}{1} \frac{n+2}{2}...\frac{m+n}{n}$

 

코드로 구현하면 아래와 같다.

fn answer2(n:i32, m:i32) -> u64{     
    let mut large:u64 = n as u64;
    let mut small:u64 = m as u64;
    if m > n { large = m as u64; small=n as u64; }

    let mut p:u64 = 1; //product     
    for i in 1..=small {        
        p *= large + i;
        p /= i;
    }
    return p;
}

 

 

총평

---

다이내믹 문제이다. 단, 메모이제이션을 사용해야 속도가 나온다.

 

그냥 조합 문제로 풀어도 된다. 

 

전체 소스코드

---

p15.rs 

#[test]
fn test(){
    assert_eq!(2, answer(1, 1));
    assert_eq!(6, answer(2, 2));
    assert_eq!(10, answer(3, 2));
    assert_eq!(137846528820 % 1000000007, answer(20, 20));
    assert_eq!(159835829, answer(500, 500));
}

#[cfg(test)]
use std::collections::HashMap;

#[cfg(test)]
fn answer(n:i32, m:i32) -> u64{
    let mut cache:HashMap<(i32,i32), u64> = HashMap::new();    
    return path(n, m, &mut cache);
}

#[cfg(test)]
fn path(y:i32, x:i32, cache:&mut HashMap<(i32,i32), u64>) -> u64 {   
    match (x,y) {
        (0,0) => return 0,
        (0,_) => return 1,
        (_,0) => return 1,
        (_,_) => {
            if let Some(val) = cache.get(&(x, y)) {
                return *val;
            }else{
                let cnt = (path(x-1, y, cache) + path(x, y-1, cache)) % 1000000007;
                cache.insert((x,y),cnt);
                return cnt;                 
            }                        
        },
    }
}

//-------------------------------
// 리스트 이용
#[test]
fn test1(){
    assert_eq!(2, answer1(1, 1));
    assert_eq!(6, answer1(2, 2));
    assert_eq!(10, answer1(3, 2));
    assert_eq!(137846528820 % 1000000007, answer1(20, 20));
    assert_eq!(159835829, answer1(500, 500));
}

#[cfg(test)]
fn answer1(n:i32, m:i32) -> u64{
    let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
    
    for i in 0..=n as usize { g[i][0] = 1;}
    for j in 0..=m as usize { g[0][j] = 1;}

    for i in 1..=n as usize {
        for j in 1..=m as usize{
            // g[i][j] = g[i-1][j] + g[i][j-1];
            g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
        }
    }
    return g[n as usize][m as usize];
}

//-----------
// n+m개에서 m개를 고르는 문제
// C(m+n, m) = (m+n)! / m!(m+n-m)! = (m+n)!/m!n!, C(m+n,n) = (m+n)! / n!(m+n-n)! = (m+n)!/n!m!
// if m>=n, (m+n)!/m!n! = (m+n) * (m+n-1) * .. * (m+1) / n!
// m=3 n=2, 5*4/2*1
#[test]
fn test2(){
    assert_eq!(2, answer2(1, 1));
    assert_eq!(6, answer2(2, 2));
    assert_eq!(10, answer2(3, 2));
    assert_eq!(137846528820, answer2(20, 20));
    assert_eq!(10, answer2(500, 500));
}

#[cfg(test)]
fn answer2(n:i32, m:i32) -> u64{     
    let mut large:u64 = n as u64;
    let mut small:u64 = m as u64;
    if m > n { large = m as u64; small=n as u64; }

    let mut p:u64 = 1; //product     
    for i in 1..=small {        
        p *= large + i;
        p /= i;
    }
    return p;
}

//---------
#[test]
fn test_cmp(){
    for i in 1..=20 {
        for j in 1..=20{
            let a = answer2(i,j);
            let b = answer1(i,j);
            if a != b {
                println!("i={}, j={}, answer2={}, answer1={}", i, j, a, b);
            }
        }
    }
}

 

끝