외발 뛰기

풀이

완전 탐색 알고리즘

우선 무식하게 푸는 방법을 생각해 봅시다. 동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것입니다. 완전 탐색 알고리즘은 맨 왼쪽 윗 칸에서 시작하는 모든 경로를 하나씩 만들어 보면서 마지막 칸에 도달할 수 있는지 검사합니다. 다음과 같은 형태의 재귀 함수를 만들어 봅시다.
$jump(y, x)=(y, x)$

public static n;
public static int[][] board;
public boolean jump(int row, int column) {
	// 기저 사례: 게임판 밖을 벗어난 경우
    if (row >= n || column >= n) return false;
    // 기저 사례: 마지막 칸에 도착한 경우
    if (row == n - 1 && column == n - 1) return true;
    int jumpSize = board[row][column];
    return jump(row + jumpSize, column) || jump(row, column + jumpSize);
}

메모이제이션 적용하기

"원하는 답이 존재하는가?"라는 질문을 완전 탐색으로 구할 때 흔히 가장 문제가 되는 것은, 원하는 답은 없는데 전체 답의 개수는 매우 많은 경우입니다. 만약 아무리 노력해도 끝에 도달할 수 없는 게임판일 경우일지라도 완전 탐색은 어떤 경로는 마지막 칸에 도달할지도 모른다고 생각하고 수없이 많은 경로들을 일일이 탐색합니다. 완전 탐색이 포기하기 전까지 만들어야 하는 경로의 개수는 $n$에 대해 지수적으로 늘어나므로, $n = 100$

public static int n;
// 아직 계산되지 않은 상태임을 저장히기 위해 boolean이 아닌 int로 저장합니다.
public static int[][] cache[100][100];
public int jump2(int row, int column) {
	// 기저 사례 처리
    if (row >= n || x >= n) return 0;
    if (y == n - 1 && x == n - 1) return 1;
    // 메모이제이션
    if (result != -1) return cache[row][column];
    int jumpSize = board[row][column];
    return cache[row][column] = (jump2(row + jumpSize, column) | jump2(row, column + jumpSize));
}

구현

import java.util.*;

public class Main {

    // 게임판의 크기입니다.
    public static int n;
    // 게임판입니다.
    public static int[][] board;
    // 캐시입니다.
    public static int[][] cache;
    // 답입니다.
    public static String result;

    // 입력값을 받는 메소드입니다.
    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        board = new int[n][n];
        cache = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
    }

    // 문제를 해결하기 위한 메소드입니다.
    public static void solve() {
        if (jump(0, 0) == 1) {
            result = "YES";
        } else {
            result = "NO";
        }
    }

    // 시작 위치에서 끝까지 갈 수 있는지 알려주는 메소드입니다.
    public static int jump(int row, int column) {
        // 기저 사례: 범위를 벗어난다면 0을 반환합니다.
        if (row >= n || column >= n) return 0;
        // 기저 사례:  만약 끝에 도달했다면 1을 반환합니다.
        if (row == n - 1 && column == n - 1) return 1;
        // 메모이제이션
        if (cache[row][column] != -1) return cache[row][column];
        int jumpSize = board[row][column];
        return cache[row][column] = (jump(row + jumpSize, column) | jump(row, column + jumpSize));
    }

    // 답을 출력하는 메소드입니다.
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고