알고리즘 수업 - 행렬 경로 문제 2

서준이는 오늘도 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제로 확인해 보자.

양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수를 모두 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.

• 오른쪽이나 아래쪽으로만 이동할 수 있다.
• 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

행렬의 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제의 의사코드는 아래와 같다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 행렬의 크기 n과 행렬 m이 주어진 경우 코드1과 코드2의 실행 횟수를 출력하자.

행렬 경로 문제의 재귀호출 의사 코드는 다음과 같다.

matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
    return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) {  # (1, 1)에서 (i, j)에 이르는 최고 점수를 구한다.
    if (i == 0 or j == 0) then
        return 0; # 코드1
    else
        return (mij + (max(matrix_path(m, i-1, j), matrix_path(m, i, j-1))));
}

행렬 경로 문제의 동적 프로그래밍 의사 코드는 다음과 같다.

matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
    for i <- 0 to n
        d[i, 0] <- 0;
    for j <- 1 to n
        d[0, j] <- 0;
    for i <- 1 to n
        for j <- 1 to n
            d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]);  # 코드2
    return d[n, n];
}

첫째 줄에 행렬의 크기 n(5 ≤ n ≤ 1,000)이 주어진다.

그 다음 n개의 줄에는 각 줄마다 행렬의 각 행을 나타내는 n개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 1 이상 100,000 이하이다.

코드1과 코드2의 실행 횟수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.