[Java] 백준 24426. 알고리즘 수업 - 행렬 경로 문제 3

📌문제 링크 - https://www.acmicpc.net/problem/24426

 

 

---

 

 

 

 

 

 

문제

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

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

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

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

 

 

 

 

 

 

---

 

 

풀이

문제를 해결하기 위해 점수를 저장할 세 개의 배열을 사용한다.

 

1. dp : 출발점에서 도착점까지 가능한 모든 경로에서의 최고 점수를 저장

2. fromY : 중간 원소(Y)를 반드시 거쳐 도착점까지 가는 경로의 최고 점수를 저장

3. excludeY : 중간 원소(Y)를 거치지 않고 도착점에 도달하는 경로의 최고 점수를 저장

 

• dp 배열을 이용해 모든 위치에서의 최고 점수를 갱신한다. (1, 1)에서 시작하여 이전 경로(왼쪽이나 위쪽의 점수) 중 더 큰 점수에 현재 위치의 값을 더해 저장해 준다.
• exclueY는 중간 원소를 제외하고 최고 점수를 갱신하기 때문에 중간 원소의 위치인 (yr, yc)는 제외하고, 이후에는 이전 경로의 점수 최댓값이 1 이상인 경우에만 값을 갱신해 준다. (경로를 보장하기 위해)
• fromY를 통해 (yr, yc)에서 시작해 도착점까지의 최고 점수를 구해준다. fromY[yr][yc] = dp[yr][yc]로 초기화해준 후 이전 경로 중 더 큰 점수에 현재 위치의 값을 더해 저장해 주며 최고 점수를 저장한다.

 

마지막으로 fromY[N][N]과 exclueY[N][N]을 출력해 주면 된다.

 

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 https://www.acmicpc.net/problem/24426
 알고리즘 수업 - 행렬 경로 문제 3

 1) 출발 원소에서 출발해서 중간 원소 Y를 거쳐서 도착 원소에 도달하는 가장 높은 점수
 2) 정수는 출발 원소에서 출발해서 중간 원소 Y를 거치지 않고 도착 원소에 도달하는 가장 높은 점수
*/
public class Main {
    private static int N;
    private static int yr, yc;
    private static int[][] map;


    public static void main(String[] args) throws IOException {
        init();
        getScore();
    }//main


    private static void getScore() {
        int[][] dp = new int[N+1][N+1]; // 전체 점수
        int[][] fromY = new int[N+1][N+1]; // 중간 원소를 거치는 점수
        int[][] excludeY = new int[N+1][N+1]; // 중간 원소 거치지 않는 점수
        excludeY[1][1] = map[1][1];

        for(int r=1; r<=N; r++) {
            for(int c=1; c<=N; c++) {
                dp[r][c] = Math.max(dp[r-1][c], dp[r][c-1]) + map[r][c];

                if((r == 1 && c == 1) || (r == yr && c == yc)) continue;

                int fromTop = excludeY[r-1][c] > 0 ? excludeY[r-1][c] + map[r][c] : 0;
                int fromLeft = excludeY[r][c-1] > 0 ? excludeY[r][c-1] + map[r][c] : 0;

                excludeY[r][c] = Math.max(fromTop, fromLeft);
            }
        }

        fromY[yr][yc] = dp[yr][yc];
        for(int r=yr; r<=N; r++) {
            for(int c=yc; c<=N; c++) {
                if(r == yr && c == yc) continue;

                fromY[r][c] = Math.max(fromY[r-1][c], fromY[r][c-1]) + map[r][c];
            }
        }


        // 1. Y를 거쳐서 가장 높은 점수   2. Y를 거치지 않고 가장 높은 점수
        System.out.printf("%d %d", fromY[N][N], excludeY[N][N]);
    }//getScore


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];

        StringTokenizer st;
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 중간 원소 Y의 행 번호 r과 열 번호 c가 주어진다.
        st = new StringTokenizer(br.readLine());
        yr = Integer.parseInt(st.nextToken());
        yc = Integer.parseInt(st.nextToken());

        br.close();
    }//init


}//class