BOJ 1890 - 점프 문제풀이

문제를 읽고 이해하기

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

 

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.

 

한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

 

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63 - 1보다 작거나 같다.

 

재정의와 추상화

일단 이 문제의 목표는 가장 위쪽 위 칸(arr[0][0])에서 가장 오른쪽 아래 칸(arr[n - 1][n - 1])으로 가는 것이다. 각 칸에는 현재 위치로부터 오른쪽 또는 아래쪽으로 이동할 수 있는 칸의 수가 적혀있다.

 

arr[0][0]부터 시작하여 각 칸의 수 만큼 오른쪽으로 이동한 곳에서, 그리고 아래쪽으로 이동한 곳에서 이곳이 arr[n - 1][n - 1]인지 아닌지 체크한다. 만약 아니라면, 또 다시 이 과정을 반복해서 arr[n - 1][n - 1]로 이동한다.

 

반복문(Bottom-up)으로 풀 수 있을까 생각하다가 힘들 것 같다는 판단을 내렸고, 결국 재귀(Top-down)으로 알고리즘을 구성했다.

 

재귀함수는 arr[y][x]에서 y, x와 게임판의 한 변의 길이 n을 매개변수로 하는 함수 dp(int y, int x, int n)이다. 이 함수는 현재 위치에서 y와 x가 n - 1인지 아닌지 확인하는 함수이다. 작동 방식은 아래와 같다.

 

1. 매개변수로 들어온 y와 x가 n - 1인지 아닌지 검사합니다. 맞다면 1을 리턴합니다.
2. 아니라면, y와 x가 n보다 작은지, 또 0은 아닌지 검사합니다.
   그 이유는 y와 x가 n보다 크거나 같으면 N×N 게임판의 범위에서 벗어납니다. (0 <= y, x <= n - 1)
   또, 0이 된다면 문제에서 진행을 막는 종착점이라고 하였으므로, 더 이상 진행해서는 안됩니다.
3. 현재 위치에 들렸던 적이 있는지 검사합니다. 들렸던 적이 있으면 더 이상 진행하지 않고 cache[y][x]에서 값을 꺼내와 리턴합니다.
   이는 재귀를 이용한 dp에서 메모이제이션 작업에 해당합니다. 이 작업이 없으면 시간 초과가 발생합니다.
4. 현재 위치에 들렸던 적이 없으면 오른쪽으로 특정 수만큼 이동한 거리, 아래쪽으로 특정 수만큼 이동한 거리에서 이 과정을 반복하고 그 결과물들을 더한 값을 리턴합니다.

 

추가적으로 문제에서 경로의 개수는 최대  2^63 - 1개까지 나온다고 하였으므로, 이 범위까지 수용할 수 있는 long long int형으로 cache를 선언해주어야 한다. arr는 0부터 9까지이므로 int로 해도 된다.

 

코드 작성

#include <iostream>

using namespace std;

long long int cache[100][100];
long long int arr[100][100];

long long int dp(int y, int x, int n) {
    if (y == n - 1 && x == n - 1)
        return 1;
    if (!(x < n && y < n) || arr[y][x] == 0)
        return 0;

    auto & ref = cache[y][x];
    if (ref)
        return ref;

    ref = dp(y + arr[y][x], x, n) + dp(y, x + arr[y][x], n);
    return ref;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    cout << dp(0, 0, n);
    return 0;
}