[JAVA] 백준 1103 게임_DP

 

문제 : 

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

 

 

접근 : 

 

  - 현재까지의 도달한 값을 dp 에 저장

 

  - 4방향으로 탐색을 실행 후, 만약 다음값이 dp 보다 크다면 더이상 탐색을 진행하지 않는다.

   > 이미 다른 경로를 통하여 해당 위치에 왔을때, 이전에 지나온 길이가 긴 것의 결과가 무조건 큰 수가 나오기 때문

   >  ex) before + after = res 라고 할때 before 가 큰 res가 무조건 더 크기 때문 (after 는 같은 값)

 

  - 만약 다음 값이 H인 경우에도 더이상 탐색을 진행하지 않는다.

 

  - 방문한 노드를 다시 방문한 경우에는 cyle이 생성되서 무한이므로 -1을 리턴한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드 구현 : 

 

import java.io.*;

public class Main {
    private static int[][] map;
    private static int[][] dp;
    private static boolean[][] visited;
    private static Position[] dir;
    private static int res;
    private static class Position{
        private final int x;
        private final int y;

        public Position(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return x;
        }
        public int getY() {
            return y;
        }

    }
    private static void dfs(Position now, int count){
        int val = map[now.getX()][now.getY()];
        int nx, ny;
        if(res == -1) return;
        dp[now.getX()][now.getY()] = count;
        res = Math.max(res, count);

        for(Position d : dir){

            nx = now.getX() + val*d.getX();
            ny = now.getY() + val*d.getY();

            if(nx < 0 || ny  < 0 || nx >= map.length || ny >= map[0].length) continue;

            if(visited[nx][ny]) {
                res = -1;
                return ;
            }
            if(map[nx][ny] == -1) continue;
            if(dp[nx][ny] > count) continue;

            visited[nx][ny] = true;
            dfs(new Position(nx, ny), count+1);
            visited[nx][ny] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);
        dir = new Position[]{
                new Position(0,1), new Position(1,0), new Position(0,-1), new Position(-1,0)
        };

        dp = new int[n][m];
        map = new int[n][m];
        visited = new boolean[n][m];
        res = 0;
        String temp;
        for(int i = 0 ; i < n ; i++){
            temp = br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j] = (temp.charAt(j) == 'H') ? -1 : (temp.charAt(j) - '0');
            }
        }

        dfs(new Position(0,0),1);
        System.out.println(res);
        br.close();
    }
}