외발 뛰기

풀이

완전 탐색 알고리즘

우선 무식하게 푸는 방법을 생각해 봅시다. 동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것입니다. 완전 탐색 알고리즘은 맨 왼쪽 윗 칸에서 시작하는 모든 경로를 하나씩 만들어 보면서 마지막 칸에 도달할 수 있는지 검사합니다. 다음과 같은 형태의 재귀 함수를 만들어 봅시다.
$jump(y, x)=(y, x)$에서부터 맨 마지막 칸까지 도달할 수 있는지 여부를 반환한다.
$jump()$는 한 번 호출될 때마다 여기에서 아래쪽으로 뛸지, 오른쪽으로 뛸지를 선택하면 됩니다. 게임판의 $(y, x)$ 위치에 있는 수를 $jumpSize$라고 하면, 각 경우 아래쪽으로 뛸 경우 마지막 칸에 도달할 수 있는지를 $jump(y + jumpSize, x)$, 오른쪽으로 뛸 경우를 $jump(y, x + jumpSize)$로 표현할 수 있습니다. 이 두 경우 중 하나만 성공해도 상관없으니 $jump(y,x)$는 다음과 같이 재귀적으로 표현할 수 있습니다.
$jump(y,x)=jump(y+jumpSize,x) || jump(y,x+jumpSize)$
아래는 이 점화식을 구현한 코드입니다.

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$이면 제한 시간을 초과해 버립니다.
여기서 주목할 것은 완전 탐색이 만드는 경로의 수는 매우 많지만 $jump()$에 주어지는 입력의 개수는 $100\times 100=10,000$개뿐이라는 사실입니다. 이 경우 비둘기집의 원리에 의해 중복으로 해결되는 부분 문제들이 항상 존재함을 알게 됩니다. $jump()$는 참조적 투명 함수이기 때문에 메모이제이션을 적용해서 중복된 연산을 없앨 수 있습니다.
아래는 메모이제이션을 적용한 코드입니다.

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();
        }
    }
}

회고