[백준] 11048. 이동하기

문제

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

풀이

문제를 보고 BFS + 다이나믹 프로그래밍으로 접근하면 되겠구나.. 라고 생각했지만, 이 방법으로 접근하는 순간 메모리 초과가 발생한다. 배열이 1000 * 1000인데, 특정 지점에서 오른쪽, 왼쪽, 대각선 아래를 탐색하기 위해서 큐에 넣고 BFS를 한다고 하면, 이미 탐색했던 지점을 여러번 방문하게 되면서 큐에 들어가게 되는 데이터가 상당히 많이 늘어나게 될 것이다. 가령 (1, 1)에 해당 탐색을 큐에 넣으면 (1,2), (2,1), (2,2) 이렇게 3개가 들어가는데, 여기서 (1,2)에 대하여 다시 3개가 들어가고, (2,1)과 (2,2)에 대하여 각각 3개씩이 들어가고, 또 들어간 원소들에 대하여 각각 3개씩 늘어나고... 를 반복하면 계산을 해보지 않아도 어마어마하게 늘어난다는 것을 알 수 있다.

BFS 기법을 사용할 때 가장 중요한 포인트는 visited 체크를 통해 이미 탐색했던 지점은 탐색하지 않고 건너 뛰게끔 구현한다는 것이다. 그렇다면 여기서 방문 체크를 해서 BFS를 이용한다면? 그럴 수 없다. (1,1) -> (1,2) -> (2,2) 의 경로와 (1,1) -> (2,1) -> (2,2) 의 경로와 (1,1) -> (2,2) 의 경로는 엄연히 별개의 것이기 때문에 한 지점을 여러번 방문할 수 있다.

사실 이 문제는 BFS를 사용할 필요가 없다. 잘 생각해보면, (1,1) ~ (1,N) 지점으로 이동하는 방법은 경로가 하나 밖에 존재하지 않는다. (1, i-1) -> (1, i) 인 경우이다. 마찬가지로 (1,1) ~ (M,1) 까지 가는 방법도 하나의 경로만 가지게 된다. 따라서 dp[y][1] = dp[y - 1][1] + map[y][1] 일 수 밖에 없고, dp[1][x] = dp[1][x - 1] + map[1][x] 밖에 없다는 것이다.

그렇다면 대각선 지점은? 사실 대각선 지점에 대한 dp 역시 간단하게 구할 수 있다. 위에서 말했듯이 

1. (x - 1, y - 1) -> (x, y - 1) -> (x, y)   

2. (x - 1, y - 1) -> (x - 1, y) -> (x, y)

3. (x - 1, y - 1) -> (x, y) 

이 3가지 경우 밖에 없다. 따라서 해당 경로에 대하여 dp 기법을 적용하면 된다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int main(){
    
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M; cin >> N >> M;
    int m[1001][1001] = { 0, };
    int dp[1001][1001] = { 0, };
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> m[i][j];
        }
    }
    dp[1][1] = m[1][1];
    for(int i = 2; i <= M; i++){
        dp[1][i] = dp[1][i - 1] + m[1][i];
    }
    for(int i = 2; i <= N; i++){
        dp[i][1] = dp[i - 1][1] + m[i][1];
    }
    for(int i = 2; i <= N; i++){
        for(int j = 2; j <= M; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
            dp[i][j] += m[i][j];
        }
    }
    
    cout << dp[N][M];
    return 0;
}