백준 11048번: 이동하기 문제 풀이 (Java)

안녕하세요! 이번에는 백준 11048번 '이동하기' 문제를 Java로 해결하는 과정을 공유하려고 합니다. 이 문제는 주어진 미로에서 가장 많은 사탕을 얻는 경로를 찾는 동적 계획법(Dynamic Programming) 문제입니다.

문제 분석

(1, 1) 위치에서 시작하여 (N, M) 위치까지 이동하면서 사탕을 줍는 문제입니다. 이동은 오른쪽, 아래, 또는 오른쪽 아래 대각선으로만 가능합니다. 각 칸에 놓인 사탕의 개수가 주어졌을 때, 얻을 수 있는 사탕의 최대 개수를 구해야 합니다.

해결 아이디어: 동적 계획법 (DP)

이 문제는 DP를 사용하기에 아주 적합합니다. dp[i][j]를 '(i, j) 위치까지 도달했을 때 얻을 수 있는 사탕의 최대 개수'라고 정의해봅시다.

(i, j) 위치로 오기 위해서는 다음 세 가지 위치 중 하나를 거쳐야 합니다.

왼쪽: (i, j-1)
위쪽: (i-1, j)
왼쪽 위 대각선: (i-1, j-1)

따라서 (i, j)까지의 최대 사탕 개수는, 위 세 위치까지의 최대 사탕 개수 중 가장 큰 값에 현재 (i, j) 위치의 사탕 개수를 더한 값이 됩니다.

이를 점화식으로 표현하면 다음과 같습니다.

dp[i][j] = arr[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

아래의 코드는 이 아이디어를 기반으로 문제를 해결합니다.

Java 코드 리뷰

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

public class Main {

    static int N,M;

    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());

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

        // dp 배열 생성 및 초기화
        int[][] dp = new int [N][M];
        dp[0][0] = arr[0][0];

        // 첫 번째 행과 열 초기화
        for(int i = 1 ; i < N ; i++){
            dp[i][0] = arr[i][0] + dp[i-1][0];
        }
        for(int i = 1 ; i < M ; i++){
            dp[0][i] = arr[0][i] + dp[0][i-1];
        }

        // 점화식을 이용한 dp 배열 채우기
        for(int i = 1 ; i < N ; i++){
            for(int j = 1 ; j < M ; j++){
                // 왼쪽과 위쪽 경로만 고려
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }

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

코드 설명

입력 처리: BufferedReader와 StringTokenizer를 사용하여 N, M과 미로의 사탕 정보를 입력받아 arr 배열에 저장합니다.
DP 배열 초기화: dp 배열을 생성하고, 시작점 dp[0][0]은 arr[0][0]으로 초기화합니다.
기저 상태(Base Case) 설정:
- 첫 번째 열(j=0)은 위에서 아래로만 이동할 수 있으므로, dp[i][0] = arr[i][0] + dp[i-1][0]로 계산합니다.
- 첫 번째 행(i=0)은 왼쪽에서 오른쪽으로만 이동할 수 있으므로, dp[0][i] = arr[0][i] + dp[0][i-1]로 계산합니다.
점화식 적용:
- i=1, j=1 부터 이중 반복문을 통해 dp 배열을 채워나갑니다.
- dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + arr[i][j]; 이 부분은 위쪽과 왼쪽에서 오는 경우 중 더 큰 값을 선택합니다.

참고: 문제의 조건은 대각선 이동(dp[i-1][j-1])도 허용합니다. 따라서 가장 정확한 점화식은 dp[i][j] = Math.max(dp[i-1][j-1], Math.max(dp[i-1][j], dp[i][j-1])) + arr[i][j]; 입니다. 하지만 이 문제의 경우, 대각선 이동은 왼쪽과 위쪽 이동의 조합으로 생각할 수 있어 제공된 코드로도 정답 처리가 됩니다.

결론

최종적으로 dp[N-1][M-1]에 저장된 값이 (N, M)까지 도달했을 때의 최대 사탕 개수입니다. 이처럼 DP를 사용하면 복잡해 보이는 경로 탐색 문제도 간단한 점화식을 통해 효율적으로 해결할 수 있습니다.