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

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

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

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

행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제 의사코드는 아래와 같다. 출발 원소 (1, 1)에서 출발해서 P개의 중간 원소 모두를 반드시 거친 후 도착 원소 (n, n)에 도달하는 가장 높은 점수를 구해서 우리 서준이를 도와주자.

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

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]);
    return d[n, n];
}

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

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

그 다음 줄에 P가 주어진다. (1 ≤ P ≤ n2 - 2)

그 다음 P개의 줄에는 각 줄마다 서로 다른 중간 원소의 행 번호 ri와 열 번호 ci가 주어진다.(1 ≤ ri, ci ≤ n, (ri, ci) ≠ (1, 1), (ri, ci) ≠ (n, n))

출발 원소 (1, 1)에서 출발해서 모든 P개의 중간 원소를 반드시 거친 후 도착 원소 (n, n)에 도달하는 가장 높은 점수를 출력한다. 도착 원소 (n, n)에 도달할 수 없는 경우 -1을 출력한다.