구리 개발소

문제:

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력:

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력:

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

풀이:

오른쪽, 아래, 대각선으로 이동가능하지만 대각선은 배제하고 생각해도 된다. 그 이유는 우선, 대각선으로 이동하기 위해서는 대각선 or 아래 -> 오른쪽 or 오른쪽 -> 아래 세 가지 길이 있다. 최대한 많은 사탕을 먹어야 하므로 지름길인 대각선 방향은 배제한다.

y와 x의 범위 체크를 위해 isValidCoord 함수를 사용했고, 아래, 오른쪽으로 이동을 표현하기 위해 구조체 dir을 만들었다.

문제를 처음 보고 나는 DFS를 떠올렸다. 그래서 DFS로 짜기 시작했는데 코드를 진행하다 보니 사탕의 양을 저장해 줄 DP가 필요하다는 것을 깨달았다. DFS와 DP를 이용해서 풀어야지 마음 먹고 다시 짜 내려갔는데 이 문제는 DFS를 쓰면 오히려 더욱 복잡해지는 문제라는 것을 알았다. 단순 완전탐색으로 DP를 활용해 진행하면 된다.

코드:

#include <iostream>
#include <algorithm>
#define DIR 2
using namespace std;

int N, M;
int Maze[1001][1001];
int DP[1001][1001];

typedef struct {
    int y, x;
} Dir;

Dir dir[DIR] = {{0,1},{1,0}};

bool isValidCoord(int y, int x) {
    return 0 <= y && y < N && 0 <= x && x < M;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> Maze[i][j];

    DP[0][0] = Maze[0][0];

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            for (int k = 0; k < DIR; ++k) {
                int dy = i + dir[k].y;
                int dx = j + dir[k].x;

                if(isValidCoord(dy, dx))
                    DP[dy][dx] = max(DP[dy][dx], DP[i][j] + Maze[dy][dx]);
            }
        }
    }

    cout << DP[N-1][M-1];
}

GIT:

https://github.com/tmsksfh2012/Algorithm/blob/main/%EB%B0%B1%EC%A4%80%2011048/main.cpp

wooder2050.medium.com/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0