[BOJ 11048] 이동하기

이 문제는 이곳에서 확인할 수 있습니다.

이 문제는 미로를 이동하면서 각 칸에 놓인 사탕을 최대 몇 개 가져올 수 있는지 구하는 문제입니다.

언뜻 보기에는 DFS나 BFS로 문제를 해결할 수 있는 것처럼 보입니다.
N과 M의 최대값은 1000이므로 미로는 최대 1,000,000칸입니다. 게다가 장애물이 없고 미로를 자유롭게 오갈 수 있으므로 출발 지점에서 도착 지점까지의 경로는 무수하게 많아지게 됩니다.
따라서 DFS나 BFS로는 시간 초과로 인해 이 문제를 해결할 수 없습니다.

이 문제를 해결하기 위해서는 DP(Dynamic Programming) 알고리즘을 사용해야합니다.
특정 지점 (A ,B) 에서 최대 사탕 개수를 구하기 위해서 (A, B) 에 도달할 수 있는 위치인 (A-1, B), (B, A-1), (A-1, B-1) 중 최대 사탕 개수 중 가장 큰 값과 (A, B) 에 놓인 사탕 개수의 합을 구하면 됩니다.

마찬가지로 (A-1, B), (B, A-1), (A-1, B-1) 에서 최대 사탕 개수를 구하기 위해서는 이전 위치 중 최대 사탕 개수 중 가장 큰 값을 구하면 됩니다.

즉 점화식은 dp[A][B] = candy[A][B] + max(dp[A-1][B], dp[A][B-1], dp[A-1][B-1]) 입니다.

인덱스가 0인 지점과 미로 바깥 부분에 대한 케이스를 잘 처리해주어야 오류가 나지 않고 문제를 해결할 수 있으니 주의해주세요!