[백준] 11048번: 이동하기 (Java)

1. 문제설명

NxM 크기의 미로가 있고, 가장 왼쪽 윗 방은 (1, 1), 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 방문하는 방의 사탕을 모두 가져갈 수 있다. 준규가 가져올 수 있는 사탕의 최댓값을 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

• DP 방법을 사용한다.
• dp 배열(2차원 배열)에 해당 칸까지 이동했을 때 얻을 수 있는 사탕의 최댓값을 저장한다.
• DP 점화식: 현재 칸에 도달할 수 있는 세 가지 경로(윗칸, 왼쪽칸, 왼쪽 위 칸)에서 가장 많은 사탕을 얻는 경로를 찾는다.
• 도착점(n-1, m-1)에서 얻을 수 있는 최대 사탕 개수를 출력한다.

 

3. 최종 코드

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

public class Main {
    static int n, m; // 미로 크기
    static int[][] miro; // 각 방의 사탕 개수 저장
    static int[][] dp; // 최대 사탕 개수 저장

    public static void main(String[] args) 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());
        miro = new int[n][m]; // 미로 배열 초기화
        dp = new int[n][m]; // dp 배열 초기화

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                // 각 방의 사탕 개수 입력받고 저장
                miro[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = miro[0][0]; // 출발 지점 초기화

        // DP를 이용해 각 칸에서 얻을 수 있는 최대 사탕 개수 계산
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(i==0 && j==0) continue;
                else if(i==0 && j>0) // 첫번째 행은 왼쪽에서만 올 수 있음
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + miro[i][j]);
                else if(i>0 && j==0) // 첫번째 열은 위쪽에서만 올 수 있음
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + miro[i][j]);
                else { // 나머지 경우는 위, 왼쪽, 대각선 왼쪽 위에서 올 수 있음
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + miro[i][j]);
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + miro[i][j]);
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + miro[i][j]);
                }
            }
        }

        System.out.println(dp[n-1][m-1]); // 도착점의 최대 사탕 개수
    }
}