[백준 c++] 1103 게임

문제

https://www.acmicpc.net/problem/1103
1~9까지의 자연수 또는 H(구멍)이 적혀있는 N x M 크기의 보드가 있다.
맨 왼쪽 위에 동전을 올려놓는다.
동전이 있는 칸에 적힌 숫자 만큼 상하좌우 방향으로 동전을 움직일 수 있다.
동전이 구멍에 빠지거나 보드를 넘어가면 게임 종료일 때,
동전을 최대 몇 번 움직일 수 있는지 구하는 문제다.
단, 동전을 무한번 움직일 수 있다면 -1을 출력한다.

시행착오

1. DFS로 풀었는데 메모리초과가 났다. 무한 반복 조건을 틀리게 설정해서 DFS가 무한히 생성되었기 때문이다.
2. 해당 설정을 제대로 고쳤지만 이번엔 시간초과가 났다.
3. DFS와 DP로 풀었다.

DP

DP로 문제를 제대로 풀어본 게 없어서 좀 힘들었다..

열심히 이해해본 결과 DP는 모든 경우의 수를 생각하면서도 계산 시간을 줄이기 위해 계산된 값을 저장해 놓아서 다시 한번 계산하는 것을 방지하는 방법이다.

이렇게 상태값을 저장해두는걸 메모이제이션이라고 한다.

풀이

    if (check[y][x])
    {
        cout << -1 << "\n";
        exit(0);
    }

무한 반복 여부를 체크하는 배열 check[y][x]가 1이면 -1을 출력하고 exit(0)을 한다.
exit(0): return과 달리 모든 남은 연산들까지 강제 종료시킨다.

---

    if (dp[y][x])
        return dp[y][x];

배열 dp에 값이 존재하면 그 값을 return한다.
연산하지 않고 바로 return하므로 시간이 절약된다.

---

    check[y][x] = 1; //방문 처리
    int v = a[y][x]; // 동전이 올려진 칸의 값
    
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i] * v;
        int nx = x + dx[i] * v;
        dp[y][x] = max(go(ny, nx) + 1, dp[y][x]);
    }
    
    check[y][x] = 0; //방문 해제
    
    return dp[y][x];

상하좌우 방향으로 움직일 좌표 ny, nx
dp[y][x] = max(go(ny, nx) + 1, dp[y][x])
움직일 좌표로 재귀 함수 호출,
dp[y][x]로 여러 값이 나올 수 있는데 그 중 최대 값을 가져야 한다.

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n, m, a[54][54], check[51][51], dp[51][51], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int go(int y, int x)
{
    if (y < 0 || x < 0 || y >= n || x >= m || a[y][x] == 0)
        return 0;
        
    if (check[y][x])
    {
        cout << -1 << "\n";
        exit(0);
    }

    if (dp[y][x])
        return dp[y][x];

    check[y][x] = 1;
    int v = a[y][x];
    
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i] * v;
        int nx = x + dx[i] * v;
        dp[y][x] = max(go(ny, nx) + 1, dp[y][x]);
    }
    check[y][x] = 0;
    return dp[y][x];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            if (s[j] == 'H')
                a[i][j] = 0;
            else
                a[i][j] = s[j] - '0';
        }
    }
    cout << go(0, 0) << "\n";
}