24426번 - 알고리즘 수업 - 행렬 경로 문제 3

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

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

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

행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제 의사코드는 아래와 같다. 출발 원소 (1, 1)에서 출발해서 중간 원소 Y를 거쳐서 도착 원소 (n, n)에 도달하는 가장 높은 점수, 출발 원소 (1, 1)에서 출발해서 중간 원소 Y를 거치지 않고 도착 원소 (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 이하이다.

그 다음 줄에 중간 원소 Y의 행 번호 r과 열 번호 c가 주어진다.(1 ≤ r, c ≤ n, (r, c) ≠ (1, 1), (r, c) ≠ (n, n))

첫째 줄에 두 정수를 출력한다. 첫 번째 정수는 출발 원소 (1, 1)에서 출발해서 중간 원소 Y를 거쳐서 도착 원소 (n, n)에 도달하는 가장 높은 점수를 의미한다. 두 번째 정수는 출발 원소 (1, 1)에서 출발해서 중간 원소 Y를 거치지 않고 도착 원소 (n, n)에 도달하는 가장 높은 점수를 의미한다.