[백준 알고리즘] 1890번: 점프

https://www.acmicpc.net/problem/3079

문제

문제

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

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

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

입력

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

출력

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

풀이

다이나믹 프로그래밍으로 풀 수 있는 문제였다. 어떤 지점 [i][j] 로 갈 수 있는 경우의 수는 [i][j] 로 갈 수 있는 지점들의 경우의 수를 합한 것과 같다는 점을 이용했다. 예를 들어 다음과 같이 입력이 주어졌다면,

1 2 1
2 1 1
1 1 0

(2, 1) 지점으로 갈 수 있는 경우의 수는 우측 라인에서 자신으로 올 수 있는 (2, 0) 경로의 경우의 수, 그리고 위쪽 라인에서 자신에게 올 수 있는 (0, 1) 과 (1, 1) 의 경우의 수를 모두 합한 것과 같다. 좌측과 아랫쪽은 아직 경우의 수를 계산하지 않은 영역이기 때문에 확인할 필요도 없고 확인할 수도 없다. 좌측, 아랫쪽 영역을 고려하지 않아도 되는 이유는 어차피 점프는 시작 위치로부터 우측방향이나 아랫쪽 방향으로 점프하는 두 가지 선택지만 존재하기 때문에 고려하지 않아도 답을 찾을 수 있다.

따라서 각 행과 열의 시작지점부터 경우의 수를 알고자하는 지점까지 오면서 점프를 통해 경우의 수를 알고자하는 지점까지 올 수 있는 경로가 있다면 해당경로까지의 경우의 수를 카운터 변수에 담고 위쪽과 왼쪽을 합쳐주는 것으로 현재 필요한 경우의 수를 알아냈다.

모든 좌표의 시작은 1로 지정했다. 0부터 시작하게 되면 outofbound 에 대한 예외처리를 해주어야 하기 때문에, 모든 0 이 들어간 좌표는 0으로 초기화 되고, 시작점은 언제나 하나의 경우의 수로 도착할 수 있기 때문에 1로 설정해주었다.

코드

#include <iostream>

using namespace std;

typedef unsigned long long ull;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int N;
    int map[101][101];
    ull dp[101][101];

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
        }
    }

    dp[1][1] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == 1 && j == 1)
                continue;
            {
                ull rowCount = 0;
                ull colCount = 0;
                for (int row = 1; row < i; row++)
                {
                    if (map[row][j] == i - row)
                    {
                        rowCount += dp[row][j];
                    }
                }
                for (int col = 1; col < j; col++)
                {
                    if (map[i][col] == j - col)
                    {
                        colCount += dp[i][col];
                    }
                }

                dp[i][j] = rowCount + colCount;
            }
        }
    }
    cout << dp[N][N];
}