백준 1103 게임 c++ // 경우의수 dp, 사이클검사방법

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

 

1. 사이클검사방법

1. 방문한 좌표를 재방문했으면, 사이클이 있는것이다!!

 

2.

중앙의 y,x에서 출발한경우, vis[y][x]=1 걸고들어간다

탐색하면서 봤는데 vis[y][x]=1 이면, 빨간색경로로 갔다온것이다, 싸이클이 있는것임.

이후, 원복을 해줘야함!

원복안하는경우 : 우측의 2가 vis되있고, 다른경로(빨간경로)에서 2를 방문하면 사이클이 있는것으로 판단해버린다...

 

3. 의사코드

if(visited) -1출력, 종료

 

visited = 1;

상하좌우 탐색

visited = 0; 

 

2. 시행착오

1. -1검사과정에서 상하좌우 같은수가 있으면 -1을 리턴하도록 했는데 이경우는

1 1

1 1 에서는 먹히지만

3 5 5 2

5 5 5 5

2 5 5 3 에서는 오답이다.

 

3. 의사코드

1. dfs(y,x) : 해당좌표, 그 상태일때 움직인 최대횟수

2. 상하좌우탐색 && dp에 최대값 저장

3. 사이클검사 : 탐색전 vis걸고, 탐색후 vis풀고, vis걸려있으면 사이클임

 

4. 전체코드

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

typedef long long ll;

ll n,m, a[54][54], dp[54][54], vis[54][54];

//좌표 : 그상태일때, 움직인 최대 횟수
ll dfs(int y, int x) {
    if (y < 0 || x < 0 || y >= n || x >= m) return 0;
    if (a[y][x] == -1) return 0;

    //사이클검사방법
    //방문한곳을 재방문했다면 사이클임!
    if (vis[y][x]) {
       cout << -1;
       exit(0);
   }
    if (dp[y][x] != -1) return dp[y][x];
    //if (dp[y][x][cnt] >= 1e9) {
    //    cout << -1;
    //    exit(0);
    //}

    //방문걸고
    vis[y][x] = 1;
    //cout << y << " " << x << " \n";
    dp[y][x] = 0;
    ll a1 = dfs(y + a[y][x], x) + 1;
    ll b = dfs(y , x+ a[y][x] ) + 1;
    ll c = dfs(y - a[y][x], x)  + 1;
    ll d = dfs(y, x- a[y][x] ) + 1;
    vis[y][x] = 0; //방문풀기 (원복해야 다른 결과에 영향을 안미침)

    vector<int> v;
    v.push_back(a1); v.push_back(b); v.push_back(c); v.push_back(d);
    dp[y][x] += *max_element(v.begin(), v.end());
    return dp[y][x];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n>>m;

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

    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] = -1;
            else a[i][j] = s[j] - '0';
        }
    }

    ll ret= dfs(0, 0);


    cout << ret;
    return 0;
}