[틀림] 백준 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;
}

 

* 2회독 (25.3.15.)

• 경로별 연결된 노드갯수 세는법
  • return 0
  • dfs() +1 을 기억하라.

• 사이클 검사방법
  • 다른방법없다. 꼼수 ㄴㄴ
  • vis 배열이 정답이다.
  • 원복은 필수
• 사이클 찾은후 바로 종료하는 법

if(vis[y][x]) {
   cout<<-1;
   exit(0);
}

• ret가 2개이상일때 , max 구하는법
  • vector에 담는대신 
  • 각 경우의수에대해 max 호출

ret=max(ret,dfs(y-num,x)+1);
ret=max(ret,dfs(y+num,x)+1);
ret=max(ret,dfs(y,x+num)+1);
ret=max(ret,dfs(y,x-num)+1);

• 전체코드
  • dfs가 dp 코드이다.
  • dfs2는 dp 없는코드

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

typedef long long ll;

int n,m;
int a[54][54],vis[54][54];
int dp[54][54]; // ->, 세로, 대각
int ret;

int dfs(int y, int x) {
   if(y<0 || x<0 || y>=n || x>=m) {
      // ret=max(ret,cnt);
      return 0;
   }
   if(a[y][x]==-1) {
      // ret=max(ret,cnt);
      return 0;
   }
   if(vis[y][x]) {
      cout<<-1;
      exit(0);
   }
   // cout<<y<<" "<<x<<"\n";
   
   int & ret = dp[y][x];
   if(ret!=-1) {
      return ret;
   }
   ret=0;
   
   int num=a[y][x];
   vis[y][x]=1;
   ret=max(ret,dfs(y-num,x)+1);
   ret=max(ret,dfs(y+num,x)+1);
   ret=max(ret,dfs(y,x+num)+1);
   ret=max(ret,dfs(y,x-num)+1);
   vis[y][x]=0;
   return ret;
}

void dfs2(int y, int x, int cnt) {
   
   if(y<0 || x<0 || y>=n || x>=m) {
      ret=max(ret,cnt);
      
      return;
   }
   if(a[y][x]==-1) {
      ret=max(ret,cnt);
      return;
   }
   cout<<y<<" "<<x<<" "<<cnt<<"\n";
   

   int num=a[y][x];
   dfs2(y-num,x, cnt+1);
   dfs2(y+num,x, cnt+1);
   dfs2(y,x+num, cnt+1);
   dfs2(y,x-num, cnt+1);
   return;
}

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

   cin>>n>>m;
   for(int i=0;i<n;++i) {
      string tmp;
      cin>>tmp;
      for(int j=0;j<m;++j) {
         if(tmp[j]=='H') {
            a[i][j]=-1; //구멍
            continue;
         }
         a[i][j]=tmp[j]-'0';
      }
   }
   // for(int i=0;i<n;++i) {
   //    for(int j=0;j<m;++j) {
   //       cout<<a[i][j]<<" ";
   //    }cout<<"\n";
   // }
   memset(dp,-1,sizeof(dp));

   cout<<dfs(0,0);
   // dfs2(0,0,0);
   // cout<<ret;
   // cout<<dfs(0,0,0);
   // cout<<ret;
}