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

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

 

 

---

 

 

 

 

 

문제

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

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

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

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

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

 

 

입력

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

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

그 다음 줄에 P가 주어진다. (3 ≤ P ≤ min(100, n))

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

 

 

 

출력

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

 

 

 

 

 

---

 

 

풀이

중간 원소를 반드시 세 개 이상 거쳐야 하므로 3차원 배열을 사용해 확인해 준다.

P = 3

배열의 크기는 dp[N+1][N+1][P+1]로, 중간 원소를 최대 3개까지 거치는 경우를 추적한다.

 

dp[r][c][p] : (r, c)에서 중간 원소를 p개 거쳤을 때의 최고 점수를 저장해 준다.

 

 

                fromTop = dp[r-1][c]; // 위
                fromLeft = dp[r][c-1]; // 왼쪽

                // 중간 원소를 0~P개 거쳤을 때 최고 점수 갱신
                for(int p=0; p<=P; p++) {
                    // 위쪽 또는 왼쪽에서 오는 최고 점수
                    int max = Math.max(fromTop[p], fromLeft[p]);
                    // 현재 위치의 점수를 더해 갱신
                    if(max > 0) dp[r][c][p] = max + map[r][c];
                }

for문을 돌며 중간 원소를 0개 ~ P개 거쳤을 때 최고 점수를 갱신해 준다.

 

 

 

                // 현재 원소가 중간 원소임
                if(isP[r][c]) {
                    // 역순으로 갱신 (현재 원소를 포함해 1~3개 거친 경우)
                    for(int p=P-1; p>=0; p--) {
                        // 위쪽 또는 왼쪽에서 오는 최고 점수
                        int max = Math.max(fromTop[p], fromLeft[p]);
                        // 중간 원소를 거친 점수 갱신
                        if(max > 0) dp[r][c][p+1] = max + map[r][c];
                    }
                }

만약 현재 위치가 중간 원소라면, 해당 원소를 지나칠 때 중간 원소의 개수를 증가시키며 점수를 갱신한다.

 

 

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/24428
public class Main {
    private static int N; // 행렬의 크기
    private static int[][] map;
    private static boolean[][] isP; // 중간 원소 여부


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

        int max = getMax();
        System.out.print(max);
    }//main


    private static int getMax() {
        int P = 3; // 적어도 세 개의 원소를 반드시 거쳐야 함
        int[][][] dp = new int[N+1][N+1][P+1]; // 0 ~ 3개를 거쳤을 때 가장 높은 점수
        dp[N][N][P] = -1; // 도착 여부를 확인하기 위해 -1로 초기화
        dp[1][1][0] = map[1][1]; // 시작점 초기화

        int[] fromTop;
        int[] fromLeft;

        for(int r=1; r<=N; r++) {
            for(int c=1; c<=N; c++) {
                if(r == 1 && c == 1) continue;

                fromTop = dp[r-1][c]; // 위
                fromLeft = dp[r][c-1]; // 왼쪽

                // 중간 원소를 0~P개 거쳤을 때 최고 점수 갱신
                for(int p=0; p<=P; p++) {
                    // 위쪽 또는 왼쪽에서 오는 최고 점수
                    int max = Math.max(fromTop[p], fromLeft[p]);
                    // 현재 위치의 점수를 더해 갱신
                    if(max > 0) dp[r][c][p] = max + map[r][c];
                }

                // 현재 원소가 중간 원소임
                if(isP[r][c]) {
                    // 역순으로 갱신 (현재 원소를 포함해 1~3개 거친 경우)
                    for(int p=P-1; p>=0; p--) {
                        // 위쪽 또는 왼쪽에서 오는 최고 점수
                        int max = Math.max(fromTop[p], fromLeft[p]);
                        // 중간 원소를 거친 점수 갱신
                        if(max > 0) dp[r][c][p+1] = max + map[r][c];
                    }
                }
            }
        }

        // (N, N)에 P개 이상의 중간 원소를 거쳤을 때 최고 점수
        return dp[N][N][P];
    }//getMax


    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];
        isP = new boolean[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());
            }
        }

        // P개의 중간 원소
        int P = Integer.parseInt(br.readLine());
        for(int i=0; i<P; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            isP[r][c] = true;
        }

        br.close();
    }//init


}//class