[백준] 1890. 점프

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오

풀이

dfs + 메모이제이션 방식으로 처음에 접근을 했다 그런데 무수한 메모리 초과 에러가 나왔다.

도저히 이해가 되지 않아 왜 그러지 .. 생각해본 결과

경로의 개수는 263-1보다 작거나 같다.

라는 사소한 경고 문구가 하나 있었다.
나중에 보니 방문 처리를 하지 않아 끝까지 도달하는 길이 없는 좌표를 여러 번 방문 했기 떄문이었다. (이것때문에 하루를 날렸다)

풀이는 다음과 같다.

---

1. 먼저 dfs 할 때 사용할 2차원 배열을 준비한다.
2. 탐색할 때마다 방문 표시를 해준다. ( -1 로 초기화 한다음, 0 으로 표시 )
3. 현재 위치에서 오른쪽 왼쪽 탐색하여 경우의 수를 업데이트 해준다.
4. 탐색 했는데 이미 방문한 곳이면 더이상 탐색 안하고 메모한 값을 꺼낸다.

---

코드

import java.io.*;
import java.util.*;
public class dfd {
    static int [][] map ;
    static long [][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        memo = new long[n][n];


        for(int i = 0 ;i < n ;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0 ;j < n ;j ++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(memo[i],-1);
        }
        //출발 경로 (0,0)
        bw.write(helper(0,0) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    public static long helper(int x, int y){

       // System.out.println(memo[x][y]);
        if(memo[x][y] != -1 ) //방문처리
            return memo[x][y];
        if(x == map.length-1 && y == map.length-1)
            return 1;
        //long sum = 0 ;//이렇게 하면 2^61 - 1 경로가 나올때 sum 이 그만큼 할당될 수 있다..

        memo[x][y] = 0 ; //방문 처리

        //현재 적힌 수만큼 이동
        int dx = x + map[x][y];
        int dy = y + map[x][y];

        //둘다 이동 불가인 경우
        if( dx >map.length-1 && dy > map.length-1)
            return 0;

        if(dx <= map.length-1)
            memo[x][y] +=helper(dx,y);
        if(dy <= map[0].length-1 )
            memo[x][y] +=helper(x,dy);

        return memo[x][y];
    }



    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}