백준 1103번 게임 (JAVA)

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

1103번: 게임

 

 

처음에는 dfs들어갈 때 visited배열을 true로 해주고 끝날 때 false로 해주지 않아 틀렸습니다. 

그 다음으로는 DP를 적용시키지 않아서 시간초과가 나왔습니다.

일반적인 경로 DP로 짜게되면 무한문이 발생하여 스택오버플로우가 발생할 수 있습니다. 그래서 visited배열과 DP배열을 같이 사용하였습니다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1103 {
    static int n,m;
    static char map[][];
    static boolean visited[][];
    static int dy[] = {-1,0,1,0};
    static int dx[] = {0,1,0,-1};
    static int dp[][];
    static int dfs(int y ,int x){
//        System.out.println(y+" "+x);
        if(visited[y][x]){
//            System.out.println(y+" "+x);
            return -1;
        }
        if(dp[y][x] != 0){
            return dp[y][x];
        }
        visited[y][x] = true;
        int result = 1;
        int num = map[y][x] - '0';
        int temp = 0;
        for(int i = 0 ; i < 4; i++){
            int ny = y + num * dy[i];
            int nx = x + num * dx[i];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[ny][nx] != 'H'){
                int now = dfs(ny,nx);
                if(now == -1){
                    result = -1;
                    break;
                }else{
                    temp = Math.max(temp,now);
                }
            }
        }
        if(result != -1){
            result += temp;
        }
        visited[y][x] = false;
        dp[y][x] = result;
        return result;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        n = stoi.apply(st.nextToken());
        m = stoi.apply(st.nextToken());
        map = new char[n][m];
        visited = new boolean[n][m];
        dp = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            String command = br.readLine();
            for(int j = 0 ; j < m; j++){
                map[i][j] = command.charAt(j);
            }
        }
        System.out.println(dfs(0,0));
    }
}