📖 [백준알고리즘 풀이] Q.11048 이동하기 문제 풀이

📖 문제

https://www.acmicpc.net/problem/11048

🔍 접근법

Q.11048 이동하기 문제 풀이입니다.

미로를 이동하며 N,M 까지 이동할 때 가져올 수 있는 사탕 개수의 최대값을 구하는 문제입니다.

처음에는 그래프 탐색 알고리즘인 bfs , dfs 를 통해 접근했으나 최단거리가 아닌

최대 사탕의 개수를 구하기 위해 다른 경로를 거쳐 온 경우도 살펴봐야 하고 경우의 수가 너무 많았습니다.

그리고 미로에 장애물과 같은 방해물 없이 오른쪽, 아래쪽, 대각선 아래 모든 경우로

움직일수 있으므로 동적프로그래밍을 통해 풀이하였습니다.

r,c 위치로 올 때 바로 위에서 오냐 왼쪽에서 오냐 대각선 왼쪽 위에서 오는 경우 중 이미

가장 많은 개수의 사탕을 확보한 쪽에서 오면 최대값이 됩니다.

dp[i][j] = MAX(dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1] ) + area[i][j]

그러나 여기서 대각선 경우는 볼 필요가 없게 됩니다.

왜냐하면 이미 사탕의 개수는 모두 0개이상이므로 굳이 대각선으로 빠르게 내려 갈 필요 없이

오른쪽으로 이동하고 아래로 이동하는 것이 대각선으로 이동하는 것보다 많은 개수의 사탕을 확보할 수 있기 때문입니다.

그래서 결국

dp[i][j] = MAX(dp[i-1][j] , dp[i][j-1]) + area[i][j]

위와 같은 점화식으로 답을 도출할 수 있습니다.

💻 코드

package problem.dynamic;

import java.io.*;

public class Main_11048 {
    static int n;
    static int m;
    static int[][] area;
    static int dp[][];

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        solve();
        System.out.println(dp[n-1][m-1]);
        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String in[] = br.readLine().split(" ");
        n = Integer.parseInt(in[0]);
        m = Integer.parseInt(in[1]);

        area = new int[n][m];
        dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            String temp[] = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                int num = Integer.parseInt(temp[j]);
                area[i][j] = num;
            }
        }
    }

    public static void solve() {
        dp[0][0] = area[0][0];
        for(int i=1; i<n; i++){
            dp[i][0] = dp[i-1][0] + area[i][0];
        }
        for(int i=1; i<m; i++){
            dp[0][i] = dp[0][i-1] + area[0][i];
        }

        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
                int maxNum = Math.max(dp[i-1][j] , dp[i][j-1] );
                dp[i][j] = maxNum+area[i][j];
            }
        }
    }
}

Written on January 11, 2021