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

해결법

• ⭐️공백없이 문자와 숫자를 같이 입력받기
• ⭐️char to int → char - ‘0’하면 됨
• 무한번 움직일 수 있다면 -1 출력
  == 사이클이 생길 수 있음 → 사이클 판별을 위해 DFS 사용
  
• 최대 움직이는 횟수 구하기
  • 완전탐색 - 시간복잡도 주의
  • 최대한 가지치기 : 엉뚱한 곳을 탐색하지 않도록 잘라냄
    • 탐색하지 않아도 될 경우
    • 이미 탐색이 끝난 경우
    • 이미 탐색한 곳을 다시 탐색할 때 (중복탐색)

#1

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

int N,M;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
char board[51][51];
bool visited[51][51];
int dp[51][51];

int solve(int x, int y){
  if(x<0||x>=N||y<0||y>=M||board[x][y]==-1) return 0;
  if(visited[x][y]){cout<<-1<<"\n"; exit(0);}
  if(dp[x][y]) return dp[x][y];
  visited[x][y] = true;
  for(int i = 0; i<4; i++){
    int nx = x + dx[i]*(board[x][y]-'0');
    int ny = y + dy[i]*(board[x][y]-'0');
    dp[x][y] = max(dp[x][y], solve(nx,ny)+1);
  }
  visited[x][y] = false;
  return dp[x][y];
}

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') board[i][j] = -1;
      else board[i][j] = s[j];
    }
  }
  cout<<solve(0,0)<<"\n";
}

다시해보장..

제출결과