[백준] 11048 : 이동하기 (JAVA/자바)

문제

BOJ 11048 : 이동하기 - https://www.acmicpc.net/problem/11048

풀이

BFS로 풀이할 수 있을 줄 알았는데 DP로 풀이해야 한다. BFS는 시간초과가 난다.

준규가 이동할 수 있는 경로는 오른쪽, 아래, 오른쪽아래 대각선이다. 그렇지만 여기서 대각선으로 가는 경로는 오른쪽->아래와 아래->오른쪽을 거쳐가는 것보다 항상 작을 수밖에 없다.

예를 들자면, 아래와 같이 사탕이 존재한다고 하자.
1 2
3 4
(1,1)에서 (2,2)까지 가는 경로는 1->3->4, 1->2->4, 1->4가 될 수 있다. 2나 3을 거쳐가는 경로는 중간에 한 칸이 더 존재하기 때문에, 1->4로 바로 가는 것보다 같거나 크다. 즉, 대각선은 오른쪽 아래로 가는 것 또는 아래 오른쪽으로 가는 것으로 대체 가능하기 때문에 고려하지 않아도 된다.

이중 배열을 선언해 사탕을 가질 수 있는 더 큰 값을 memorization한다. 점화식은 dp[i][j] = Math.max(map[i][j]+dp[i-1][j], map[i][j]+dp[i][j-1]) 가 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);

        int[][] map = new int[N+1][M+1];
        int[][] dp = new int[N+1][M+1];
        
        for(int i=1; i<=N; i++){
            inputs = br.readLine().split(" ");
            for(int j=1; j<=M; j++){
                map[i][j] = Integer.parseInt(inputs[j-1]);
            }
        }

        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                dp[i][j] = Math.max(map[i][j]+dp[i-1][j], map[i][j]+dp[i][j-1]);
            }
        }

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

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• 문제를 딱 처음 보고는 알고스팟과 거의 비슷한 문제라고 생각했다. BFS로 주변을 탐색해가며 얻을 수 있는 사탕의 개수를 저장해서 최댓값을 구하는 방식으로 풀이했는데 시간초과가 나왔다.. 이유를 생각해보니 알고스팟에서는 최솟값을 구하는 게 문제였고, 이 문제에서는 최댓값을 구해야한다. BFS 탐색 시 최댓값은 돌고돌아오면 더 최대가 될 수 있으므로 시간초과가 날 수 있다!

• 비슷한 문제라고 자만하지 말 것,,,

참고 사이트

백준 11048 질문하기 게시판