문제

나의 요약

NxM 배열로 된 지형이 존재한다. 탐사하는 로봇은 '하, 좌, 우' 방향으로 이동이 가능하다. '상' 방향으로는 이동이 불가하다. 한번 탐사한 지역은 다시 탐사가 불가하다.
왼쪽 위에서 출발해, 오른쪽 아래에 도착할 때, 탐사한 지역들의 가치의 합이 최대인 값을 찾아 출력한다.

접근 방법

일단 N과 M이 모두 최대 1000이기 때문에, 백트래킹을 이용한 탐색 방법은 불가하다. 하지만 탐색을 진행하긴 해야하는데, 특정 좌표에서 '하, 좌, 우' 방향으로 각각 갔을 때 탐색을 한번씩만 진행해야 한다. 또한 '좌'에서 왔을 때 다시 '우'로 가거나, 그 반대의 경우는 허용되지 않아야 한다.

따라서 DP와 DFS를 결합하기로 했다. DFS를 이용해 이미 방문한 노드는 다시 방문하지 않도록 하되, 그 안에서 DP를 이용해 특정 좌표에서 특정 방향으로 갔을 때의 최대치를 미리 저장해두기로 했다. 즉 다음와 같다.
1. (0, 0)에서 DFS을 시작한다.
2. 좌표를 방문했다고 기록한다.
3. '하, 좌, 우' 방향의 인접 좌표를 방문하지 않았다면 방문한다.
4. 각 인접 좌표에서의 탐색은 '하, 좌, 우' 방향으로 이동했을 때의 최댓값 + 자신의 가치를 반환한다.
4-1. 만약 좌표가 (N-1, M-1)이라면 자신의 가치만 반환한다.
5. 좌표의 방문을 마무리한다.

재귀 형식으로 구현해야 하기 때문에 텍스트로는 잘 정리되지 않는다. 코드를 보면 더 이해가 빠를 것이다.

풀이

#include <bits/stdc++.h>
using namespace std;

const int minValue = -1000000;

// 하, 좌, 우
int dx[] = {1, 0, 0};
int dy[] = {0, -1, 1};
int DP[1000][1000][3];

int N, M;
vector<vector<int>> mars;
vector<vector<bool>> visited;

void Input()
{
    cin >> N >> M;
    mars.assign(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> mars[i][j];
        }
    }
}

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

int DFS(int x, int y, int dir)
{
    if (x == N - 1 && y == M - 1)
    {
        return mars[x][y];
    }

    if(DP[x][y][dir] != minValue)
    {
        return DP[x][y][dir];
    }

    visited[x][y] = true;

    int maxCost = minValue;
    for(int i = 0; i < 3; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(IsInMars(nx, ny) == false) continue;

        if(visited[nx][ny]) continue;
        maxCost = max(maxCost, DFS(nx, ny, i));
    }
    DP[x][y][dir] = maxCost + mars[x][y];
    visited[x][y] = false;

    return DP[x][y][dir];
}

void Solve()
{
    visited.assign(N, vector<bool>(M, false));
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            DP[i][j][0] = DP[i][j][1] = DP[i][j][2] = minValue;
        }
    }
    cout << DFS(0, 0, 0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

DFS 함수에 집중하자. 탐색하는 좌표가 (N-1, M-1)이면, 가장 멀리까지 DFS가 온 것이니 본인의 가치를 반환한다.
이를 넘어가서, dir 방향에서 (x, y)로 왔을 때의 최댓값(DP[x][y][dir])이 전에 저장된 적이 있다면, 이 탐색이 이미 진행되었다는 뜻이다. 굳이 탐색을 진행하지 않고 저장되어 있던 값을 전달한다.

만약 탐색을 새로 진행해야하는 상황이라면, 방문했다고 저장한다. 이후 '하, 좌, 우' 방향에 대해 탐색을 진행하고, 가장 높은 값이 나온 것을 저장해 DP[x][y][dir]에 자신의 가치 값을 더해 저장한다. 이후 방문을 마무리하고, 자신의 가치 값을 더한 최댓값을 반환해준다.

회고

이 문제도 접근이 어려웠다. 처음에 DP 단일 문제로 풀 수 있을 것이라 생각했지만, 내 접근이 다소 모자랐다. 좌->우로 갔을 때의 최댓값, 우->좌로 갔을 때의 최댓값을 따로 계산해 둘 중 큰 값을 해당 좌표까지 갔을 때의 최댓값으로 기록해두면 된다고 접근했지만, 이를 실제적으로 구현하는 부분에서 살짝 머리가 터질 것 같아서.. 이후 접근 자체를 DFS로 바꿨다.

풀이한 후 여러 코드를 찾아보니 내가 생각했던 방법으로 풀이한 분들이 계셨다. 이 방법의 풀이가 궁금하다면 여기를 참고하자. 한 줄씩 차근차근 진행하는 부분이 인상적이었다. 확실히 이 방법이 O(N*M)이기 때문에, 훨씬 빠르겠다는 생각은 들었다.

접근 방향 자체는 괜찮았으나, 이후 구체화시키는 과정에서 급하게 하려다가 실패했다. 일단 방향이 맞다고 생각이 들면, 차근차근 생각하면서 구체화시켜보자.