[BOJ/C++] 1103: 게임

🏅 Gold 2

✏️ 1차 솔루션

⭐️ DFS로 풀이

1. board 의 (x,y) 값이 0 이거나 out of index 가 아니라면 (x,y) 자리에서 이어서 탐색
2. 이미 방문했을 경우, loop 발생 방지 위해 -1 return 하고 exit(0) 으로 바로 끝내버리기
3. (x,y) 방문 처리
4. ans 에 최대 이동 횟수 기록
5. ans 에 다음 칸 dfs 결과 + 1 과 ans 중에서 최대값 저장
   ➡️ 이때 1은 dfs 로 방문한 (x,y) 가 더 이상 탐색할 수 없는 경우라도 해당 위치까지는 count 해야하는데 이 경우, 경로 count 되기 전에 return 되기 때문에 더해주는 것
6. dfs return 해서 이전 단계에서 갈 수 있는 다른 방향으로 탐색 위해 (x,y) 방문 해제

🚨 1차 trouble

틀린건지 시간초과인지
최대 이동 횟수를 변수에 저장하는 것이 아니라 DP로 기록해가면서 풀이해야 함

✏️ 최종 솔루션

❗️ ans 대신 DP 사용

• 현재 탐색하고 있는 루트가 아니라면 visit 처리가 안되어 있는데 다른 루트로 탐색했을 때 미리 최대 경로를 저장해뒀다면 반복해 탐색할 필요없이 return 해서 사용하기 위함
• (x,y) 에 대한 ans 값을 DP에 저장해 두는 원리
• DP를 -1 로 초기화
  ➡️ 이미 한번 탐색했던 위치라면 -1 이 아닐 것이므로 (x,y) 에 저장된 dp 값을 return 해서 사용

✏️ 최종 code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int board[51][51];
bool visit[51][51];
int dp[51][51];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int n,m;

int dfs(int x, int y) {

    // out of index
    if(x<0 || x>=n || y<0 || y>=m || board[x][y]==0) return 0;

    // loop 발생 -> -1 출력하고 바로 죽여버리기
    if(visit[x][y]) {
        cout << -1;
        exit(0);
    }

    // 이미 방문했을 경우 return
    if(dp[x][y]!=-1) return dp[x][y];

    visit[x][y]=true;

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

        dp[x][y]=max(dp[x][y], dfs(nx, ny)+1);    // out of index도 거리에 count
    }

    // 다른 방향 탐색 위해 visit 풀어주기
    visit[x][y]=false;

    // 최종적 ans return 위해
    return dp[x][y];
}

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

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

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

    cout << dfs(0,0);
}