[백준 Silver 1] 11048 이동하기 - Java

문제링크 : https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

접근 과정 : 

• 해당 문제는 DP를 이용해서 풀수 있다.
• DP[r][c] = maze[r][c] + Math.max(dp[r-1][c], Math.max(dp[r][c-1], dp[r-1][c-1])) 이다.
• Top-down 과 Bottom-up으로 풀어보았다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    이동하기
    
    Top-down
*/

import java.io.*;
import java.util.*;

public class BOJ11048_copy {

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

        init();

        System.out.println(findDP(N, M));

    }

    static int N, M;
    static int[][] maze;
    static int[][] dp;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        maze = new int[N + 1][M + 1];
        dp = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[i], -1);
            for (int j = 1; j <= M; j++) {
                maze[i][j] = Integer.parseInt(st.nextToken());
            }
        }

    }

    static int findDP(int r, int c) {

        if (r <= 0 || r > N || c <= 0 || c > M) {
            return 0;
        }

        if (dp[r][c] != -1) {
            return dp[r][c];
        }

        return dp[r][c] = maze[r][c] + (Math.max(findDP(r - 1, c), Math.max(findDP(r, c - 1), findDP(r - 1, c - 1))));
    }
}

 

package BOJ;

/* 
    이동하기
    
    Bottom-up
*/

import java.io.*;
import java.util.*;

public class BOJ11048 {

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

        inputAndDp();

        System.out.println(dp[N][M]);

    }

    static int N, M;
    static int[][] dp;

    static void inputAndDp() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] += Math.max(dp[i - 1][j], Math.max(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }

    }
}

 

P.S 

해당 문제의 DP는 입력방향과 함께 진행할 수 있다.

그래서 입력과 동시에 Bottom-up으로 DP를 시행할 수 있었다.

 

Top-down을 할 때에는, 방문체크를 확실하게 해주어야 한다.

dp[r][c] == 0으로 방문체크를 한다면, 미로의 사탕이 모두 0개로 채워지는 최악의 경우를 만나 시간초과가 날것이다.

 

이동방향을 보고 DP를 연상할 수 있다면 쉽게 풀 수 있는 문제라고 생각한다.