백준 11048번 이동하기 (C++)

문제 링크 : https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

문제 요약

 

1. 진수는 미로의 [1,1]에서 [N,M]으로 가려고 합니다.

2. 진수의 이동방향은 진수가 (r,c)에 있다고 가정할때, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있습니다.

3. 미로의 방 중에는 사탕이 놓여진 방이 있습니다. 진수가 최대한으로 가져갈 수 있는 사탕 갯수를 구하세요.

 

핵심 포인트

 

이 문제는 BFS로도 풀 수 있지만, 간단하게 다이나믹 프로그래밍(Dynamic Programming, 동적 프로그래밍)으로도 풀 수 있습니다.

BFS는 근본적으로 갈 수 있는 곳은 모두 방문하되, 최단거리를 찾는 것이 목표입니다.

하지만 이 문제는 갈 수 있는 방향이 한정적입니다. 뒤로 돌아갈 수 없으며, 오로지 앞, 측면, 대각선 3방향으로만 이동이 가능합니다.

때문에 다이나믹 프로그래밍을 활용해 사탕을 가장 많이 갖는 루트만 저장하면 됩니다.

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력 받습니다.

또한 dp[1][1]은 v[1][1]로 저장합니다.

    int n,m,my[]={1,0,1},mx[]={0,1,1},y,x,ny,nx;
    cin >> n >> m;
    vector<vector<int>> v(n+1,vector<int>(m+1,0)); // 미로
    vector<vector<int>> dp(n+1,vector<int>(m+1,0)); // 사탕 DP
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) cin >> v[i][j];
    }
    dp[1][1] = v[1][1];

 

2. DP를 진행합니다. 구체적인 설명은 다음과 같습니다.

   for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            y = i; // 1
            x = j;
            for(int a=0; a<3; a++){ // 2
                ny = y+my[a];
                nx = x+mx[a];
                if(ny<1||ny>n||nx<1||nx>m) continue; // 3
                if(dp[y][x]+v[ny][nx]<=dp[ny][nx]) continue; // 4
                dp[ny][nx] = dp[y][x]+v[ny][nx]; // 5
            }
        }
    }

(1) 현재 위치 값을 각각의 변수에 저장합니다.

(2) 갈 수 있는 방향 3개를 따라 for문을 진행합니다.

(3) 만약 갱신된 위치가 미로의 범위를 초과한다면 continue를 합니다.

(4) 만약 갱신된 위치의 누적 사탕값이 현재 위치값 + 갱신된 위치에 놓인 사탕값 보다 작다면, continue를 합니다.

(5) 4번에 해당되지 않을 경우, 현재 새로이 갱신된 루트가 가장 많은 사탕값을 가지고 있다는 뜻입니다. 때문에 현재 위치값에서 갱신된 위치에 놓인 사탕을 먹은 값을 갱신된 위치의 누적 사탕값에 저장하면 됩니다.

 

3. dp[n][m]을 출력합니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,my[]={1,0,1},mx[]={0,1,1},y,x,ny,nx;
    cin >> n >> m;
    vector<vector<int>> v(n+1,vector<int>(m+1,0));
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) cin >> v[i][j];
    }
    dp[1][1] = v[1][1];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            y = i;
            x = j;
            for(int a=0; a<3; a++){
                ny = y+my[a];
                nx = x+mx[a];
                if(ny<1||ny>n||nx<1||nx>m) continue;
                if(dp[y][x]+v[ny][nx]<=dp[ny][nx]) continue;
                dp[ny][nx] = dp[y][x]+v[ny][nx];
            }
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}