외발 뛰기 (난이도: 하)

1. 문제 설명

(1) 아래의 그림처럼 NxN 크기의 격자에 1부터 9까지의 정수를 쓴 게임판이 있다.

(2) 이 게임의 목적은 게임판의 왼쪽 위칸에서 시작해서 게임판의 맨 오른쪽 아래칸 "끝" 쪽으로 도착하는 것이다.

 

(3) 이때 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있으며, 중간에 게임판 밖으로 벗어나면 안 된다.

 

(4) 문제는 게임판이 주어질 때 시작점에서 끝점까지 도달하는 방법이 존재하는 지를 확인하는 것이다.

 

(5) 예를 들어, 아래의 그림처럼 위의 그림에서 마지막 2를 3으로 바꾸면 방법이 없다.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에는 N(1<=N<=10)의 크기

(3) 그 후 각  줄에는 board(1<=board<=100)를 초기화한다.

 

출력 조건

(1) True는 1로, False는 0으로 출력한다.

 

입력 예제

2
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 0
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 3
3 3 1 2 3 4 1
1 5 2 9 4 7 0

 

출력 예제

1

0

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) board판의 범위를 벗어나면

 

 

 

 

6. 코드

: 동적 계획법으로 바꾸기 위해서 먼저 (1)에서는 완전 탐색을 보여주고 (2)에서는 (1)에서의 완전 탐색 중복 계산을

없애는 메모이제이션을 수행하는 것을 보여준다.

 

 

 

(1) 완전 탐색

public class JUMPGAME1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int[][] board ;
    private static int N;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            N = Integer.parseInt(sc.readLine());
            board = new int[N][N];

            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    board[y][x] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append(solve(0,0)+"\n");
        }
        System.out.println(sb);
    }

    private static boolean solve(int y, int x) {
        // 기저 사례(1): 범위를 벗어나면 false
        if(y>=N || x>=N) return false;

        // "끝" 지점에 도달한 경우 성공
        if(y==N-1 && x==N-1) return true;

        // jump 크기를 가지고 완전탐색 시작.
        int jumpSize = board[y][x];
        return solve(y+jumpSize, x) || solve(y, x+jumpSize);
    }
}

 

 

 

(2) 메모이제이션

public class JUMPGAME2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int[][] board;
    private static int N;
    private static int[][] cache;
    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            N = Integer.parseInt(sc.readLine());
            cache = new int[N][N];
            board = new int[N][N];

            // 캐시 배열 모두 -1로 초기화
            for(int y=0; y<N; y++) {
                for(int x=0; x<N; x++) {
                    cache[y][x] = -1;
                }
            }

            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    board[y][x] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append(solve(0,0)+"\n");
        }
        System.out.println(sb);
    }
    private static int solve(int y, int x) {
        // 기저 사례(1): 범위를 벗어나면 false
        if(y>=N || x>=N) return 0;

        // "끝" 지점에 도달한 경우 성공
        if(y==N-1 && x==N-1) return 1;

        // 메모이제이션
        if(cache[y][x] != -1) return cache[y][x];

        // jump 크기를 가지고 완전탐색 시작.
        int jumpSize = board[y][x];
        return cache[y][x] = (solve(y+jumpSize, x) | solve(y, x+jumpSize));
    }
}