백준 1103번: 게임

문제

문제 바로가기> 백준 1103번: 게임

풀이

삼성 SDS 알고리즘 특강 첫날 푼 문제데, 그래프랑 dp 개념이 확실히 잡혀 있는게 아닌데 같이 이용해서 풀어야한다고 하니 너무 어려웠다. 이해하고 푸는데 진짜 오래 걸렸다 ㅠㅠㅠㅠㅠ
단순 dfs만 사용하면 방문한 곳을 재방문하면서 시간을 많이 소요하기 때문에 dp를 이용하여 최대 방문횟수를 update해 나가며 풀어야 하는 문제다. 답은 update한 dp[y][x]값을 출력해주면 된다. 만약 한 번의 방문 중에 방문 한 곳을 또 방문하게 되면 cycle이 형성되는 것이므로, -1을 출력해주면 된다.

#include <iostream>
using namespace std;

int board[51][51], visited[51][51], dp[51][51];
int n, m;

// 오른쪽 왼쪽 위 아래 
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int dfs(int y, int x){
    if(y<1 || x<1 || y>n || x>m || board[y][x]==24) return 0;
    if(visited[y][x]){
        cout << -1;
        exit(0);
    }
    if(dp[y][x]) return dp[y][x];
    visited[y][x] = 1;
    for(int i=0; i<4; i++){
        int ny = y + dy[i]*(board[y][x]);
        int nx = x + dx[i]*(board[y][x]);
        dp[y][x] = max(dp[y][x], dfs(ny, nx)+1);
    }
    visited[y][x] = 0;
    return dp[y][x];
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        string str; cin>>str;
        for(int j=1; j<=m; j++) 
            board[i][j] = str[j-1]-48; // H-48==24
    }
    cout << dfs(1, 1);
}