게임 - 1103

//1103 - 게임
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 2000000000
 
int N, M;
int arr[50][50];
//북 동 남 서
int cache[50][50][4];
int xarr[4] = {-1, 0, 1, 0};
int yarr[4] = {0, 1, 0, -1};
 
void init()
{
    cin >> N >> M;
    string s;
    for(int i = 0; i<N; ++i)
    {
        cin >> s;
        for(int j = 0; j<M; ++j)
        {
            if(s[j] != 'H')
                arr[i][j] = s[j] - '0';
            else arr[i][j] = 'H';
 
            for(int k = 0; k<4; ++k)
                cache[i][j][k] = -1;
        }
    }
}
 
int dp(vector<vector<bool>>& visit, int x, int y, int way)
{
    if(arr[x][y] == 'H') return 0;
    if(x < 0 || x >= N || y < 0 || y >= M) return 0;
    if(visit[x][y]) 
        return INF;
 
    int& ret = cache[x][y][way];
    if(ret != -1)
        return ret;
    visit[x][y] = true;
    ret = 0;
    int u = arr[x][y];
    for(int i = 0; i<4; ++i)
        ret = max(ret, dp(visit, x+u*xarr[way], y+u*yarr[way], i));
    visit[x][y] = false;
    ++ret;
    return ret;
}
 
int main()
{
    init();
    vector<vector<bool>> visit(N, vector<bool>(M, false));
    int ans = 0;
    for(int i = 0; i<4; ++i)
       ans = max(ans, dp(visit, 0, 0, i));
 
    if(ans >= INF)
        cout << -1;
    else cout << ans;
}

 

 

 

 

 

 

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

1103번: 게임

 

 

 

 

 

 

게임

dp를 이용해 해결할수 있었습니다.

cache[i][j][way] : (i, j) 에서 way방향으로 동전을 보낼때 갈수있는 최대의 수

이때, INF로 도는것을 감지하기 위해 재귀함수에 VISIT배열을 넘겨주어 한번의 시도에 같은곳을 여러번 방문하는지 확인했습니다.

만약 한번의 시도에 같은곳을 다시 방문하게 된다면 그곳을 계속 돌면 INF번 돌수 있기 때문입니다.

 

(재귀함수 DP에 VISIT과 같은 flag값을 넘겨줄때, 메모이제이션으로 인해 반환되는곳 위에 flag를 변경하게 되면 flag를 초기화 시키는 부분이 실행안되기 때문에 의도와 다르게 동작할수 있다는것을 생각하고 메모이제이션으로 return되는 부분 위에는 기저사례말고 아무것도 넣지 안도록 주의해야 겠습니다.. 이것때문에 오답 제출했습니다..)