[백준] 1103 - 게임

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

1103번: 게임

 문제에서 제시하는 map의 사이즈가 최대 50x50이라 시간초과가 날 일은 없을 것이라 생각하고, DFS(깊이우선 탐색)을 통한 완전 탐색을 하면 될 줄 알았다. 그런데 문제를 다시 읽어보니 말을 움직이는데 있어 중간에 사이클이 생길 수 있네?

 사이클에 대해서는 같은 map 사이즈로 visited 배열을 선언해서 이전에 방문한 적이 있으면 -1을 출력 후 리턴을 하게 해주었는데, 같은 위치를 가더라도 어디를 거쳐서 왔는지에 대해서는 다르게 처리해줄 필요가 있었다. 결국은 DP(동적 계획법)도 필요해짐;;

 이 문제를 해결하기 위해 알고 있어야 하는 지식은, DP, DFS, 그리고 재귀 함수에 대한 구현력 정도인 것 같다.

 조금 더 문제에 대한 고민을 했더라면 꽤 많은 재시도 횟수를 줄일 수 있었을텐데 아쉽다. 그리고 MAC에서는 clang의 컴파일 기준이 백준의 체점서버와는 다르게 너무 관대하다. include하지 않은 헤더파일에 대한 컴파일 에러도 많이 발생시켰다. 조금 더 차분해질 필요가 있다.

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int solve(int y, int x){
    if(y < 1 || y > N || x < 1 || x > M || map[y][x] == 'H'){
        return 0;
    }

    if(visited[y][x] == true){
        printf("-1\n");
        exit(0);
    }
    if(dp[y][x] != -1){
        return dp[y][x];
    }
    dp[y][x] = 0;

    visited[y][x] = true;
    int step = map[y][x]-'0';
    for(int i=0; i<4; ++i){
        int ny = y + (dy[i] * step);
        int nx = x + (dx[i] * step);
        dp[y][x] = max(dp[y][x], solve(ny, nx)+1);
    }
    visited[y][x] = false;
    return dp[y][x];
}

int main(){
    memset(visited, false, sizeof(visited));
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &N, &M);
    for(int i=1; i<=N; ++i){
        char str[52];
        scanf("%s", str);
        for(int j=1; j<=M; ++j){
            map[i][j] = str[j-1];
        }
    }

    int result = solve(1, 1);
    printf("%d\n", result);

    return 0;
}