[BOJ 11048] 이동하기

#문제

https://www.acmicpc.net/problem/11048

#풀이

굉장히 쉬워보이지만 은근 까다로운 문제인것 같습니다!

처음에는 BFS를 사용하여 푸는 생각을 했지만, 해당 문제는 최단 거리를 움직여 구하는 것이 아니며, 

모든 경우의 수를 해보아야 하고 이미 지나간 자리도 다시 한번 확인을 해야합니다.

또한, N과 M이 1000이 넘어가므로 크기도 어마어마해집니다.

따라서 DP(Dynamic Programming)으로 풀었습니다.

DP의 경우 엄청 복잡한 알고리즘이 아닙니다.

혹시나 DP를 처음 접하시는 분이라면 잠깐 새 탭을 눌러 검색하여 사전 공부를 하시는 것이 좋습니다! :)

다시 문제로 들어가서! 사탕을 최대로 모아야 하며 준규가 움직이는 방향은 오른쪽, 아래, 대각선(오른쪽 아래) 총 3방향입니다.

여기서 숨어있는 점이 하나 있습니다. 

바로 대각선은 사실 필요가 없다! 입니다.

왜!? Why!? 

우리가 필요한 것은 사탕의 개수를 최대로 모으는 방법을 찾는 것입니다.

천천히 생각을 해봅시다...

만약, 아래와 같은 맵의 일부분이 있다고 해봅시다.

 

3  4

0  2

준규는 현재 (0,0):3 위치에 있다고 할 때, 대각선으로 움직이면, 총 얻는 사탕의 개수는 3 + 2 = 5개.

만약 우->아래(똑같은 대각선)로 움직였을 때는 3 + 4 + 2 = 9개 입니다.

마지막으로 아래->우로 움직였을 때는 3 + 0 + 2 = 5개 입니다.

보이시나요?

우리가 구해야되는 것은 사탕의 최대 개수이지 최단 거리를 가라! 라는 말은 없었습니다.

다른칸을 한번더 훑고 오는 방법이 거리로는 1칸을 더 가야하지만, 사탕을 최대로 얻을 수 있을 수도 있기 때문에 대각선을
무시해도 되는 것입니다.

만약, 어떠한 칸에 갔을때 사탕을 잃어버린다면..?(맵의 값이 -일때)

이때는 무조건 대각선의 방향도 넣어줘야 되겠죠?

이제 코드를 보며 이해를 해봅시다!

#코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int maze[1001][1001];
int d[1001][1001];
int N,M;
 
// 방법3: top-down, 재귀 사용.
int dp(int r, int c){
    if(r == N && c == M) return maze[r][c];     //base value
    if(r > N || c > M) return 0;                //미로의 범위를 벗어나는 조건!
    if(d[r][c] >= 0) return d[r][c];            //메모이제이션(-1로 초기화)
    
    d[r][c] = max(dp2(r+1,c), dp2(r,c+1)) + maze[r][c];
    return d[r][c];
}
 
// 방법4: 여태껏 d를 채우는 방법이 [1,1]에서 [N,M]으로 가는 것이었다면, 현재 방법은 그 거꾸로 가는 것이다.
//  top-down, 재귀
int dp2(int r, int c){
    if(r == 1 && c == 1) return maze[1][1];     //base value
    if(r < 1 || c < 1) return 0;                //미로의 범위를 벗어나는 조건!
    if(d[r][c] >= 0) return d[r][c];            //메모이제이션(-1로 초기화)
    
    d[r][c] = max(dp(r-1,c), dp(r,c-1)) + maze[r][c];
    return d[r][c];
}
 
int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> maze[i][j];
        }
    }
    // 방법1: i,j로 올수 있는 방법은 2가지
    //          위에서 올 때 : d[i-1][j]
    //          왼쪽에서 올 때 : d[i][j-1]
    // 이 세가지 방법중 제일 큰 수를 현재 위치인 i,j에 저장한다.
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            d[i][j] = max(d[i-1][j],d[i][j-1]) + maze[i][j];
        }
    }
 
    // 방법2: i,j에서 갈 수 있는 방법 2가지
    //          아래로 갈 때: d[i+1][j] = d[i][j] + maze[i+1][j]
    //          오른쪽으로 갈 때: d[i][j+1] = d[i][j] + maze[i][j+1]
    d[1][1] = maze[1][1];
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            d[i+1][j] = max(d[i+1][j], d[i][j] + maze[i+1][j]);
            d[i][j+1] = max(d[i][j+1], d[i][j] + maze[i][j+1]);
        }
    }
    cout << d[N][M] << endl;
    return 0;
}