백준 1103번. 게임(c++) / DP+DFS

DFS와 DP를 활용한 대표적인 문제이다.

it회사들에서 이러한 유형을 좋아하는 것 같다. 물론 it회사 뿐 아니라, 모든 회사에서?

그래서 연습을 많이 해두면 좋을 것 같다.

 

사이클이 형성되면 무한대로 이동이 가능하다는 것을 의미하기 때문에

사이클 형성여부를 visited배열로 표시해주었다.

즉, 이미 방문한 점을 또 방문한다면 => 사이클을 형성한 것이기 때문에 바로 -1을 출력하고 끝나도록 코드를 짰다.

 

// 게임
#include <cstring>
#include <iostream>
using namespace std;
 
int n, m;
string s;
char game[51][51];
int visited[51][51] = {0, };
int dp[51][51] = {0, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
 
int move(int x, int y)
{
    if(visited[x][y]==true){
        cout<<"-1"<<"\n";
        exit(0);
    }
 
    if(dp[x][y]!=-1){
        return dp[x][y];
    }
 
    dp[x][y] = 0;
 
    for(int i=0; i<4; i++){
        int cnt = 1;
        int num = game[x][y]-'0';
        int nx = x+dx[i];
        int ny = y+dy[i];
 
        while(cnt<num){
            nx += dx[i];
            ny += dy[i];
            cnt++;
        }
 
        if(0<=nx && nx<n && 0<=ny && ny<m){
            if(game[nx][ny]=='H') continue;
            visited[x][y] = true;
            dp[x][y] = max(dp[x][y], move(nx, ny)+1);
            visited[x][y] = false;
        }
    }
 
    return dp[x][y];
}
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>s;
        for(int j=0; j<m; j++){
            game[i][j] = s[j];
        }
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout<<move(0, 0)+1<<"\n";
    return 0;
}