백준 [C++] 1103 게임

<조건 분석>

 

1. 만약 완탐으로 해보겠다. 라고 생각한다면,4방향, 50*50보드면 4^2500 경우의 수임.

 

2. 그럼 방문처리해서 DFS 식으로 혹은 DP로 간다면 O(M*N)에 상수 4방향 해서 약 10000번 정도.

 

 

 

<문제 해결 포인트>

 

1. 방문 처리 된 곳을 방문했다면 사이클 이므로 -1을 출력하고 exit 하는 것도 방법.

 

2. DP는 DFS가 탐색하고 있는 그 경로 자체의 함수 호출스택이 경우의 수를 탐색하고 있는 거라고 생각해보면 됨.

 

3. 그렇게 생각하면 맵을 벗어났을 때는 게임이 끝난 것 이므로 경우의 수 0을 반환. go 재귀로 들어갈 때는 경우의 수 1개가 추가되는 거임.

 

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

int n, m;
int dp[50][50];
char board[50][50];
int visited[50][50];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int go(int y, int x)
{
    if (visited[y][x]) // 방문 되어 있으면 사이클
    {
        cout << -1;
        exit(0);
    }

    if ((y < 0 || x < 0 || y >= n || x >= m)  || board[y][x] == 'H')
    {
        return 0; // 게임 끝이니까 해당 좌표에서는 경우의 수가 없으므로 0 반환
    }


    int& ret = dp[y][x];
    if (ret != -1) return ret;

    int delta = board[y][x] - '0';

    visited[y][x] = 1;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i] * delta;
        int nx = x + dx[i] * delta;

        ret = max(ret, go(ny,nx) + 1); // 경우의 수 한개 추가
    }
    visited[y][x] = 0;

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
        }
    }


    cout << go(0, 0);


}