[ 백준 1890 ] 점프 (C++)

백준의 점프(1890) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예시를 통해서 문제에 접근해보자.

.

위와 같은 상황에서 (0 , 0) 에서 (N - 1 , N - 1)까지 가는 경우의 수를 파악해보자.

지금부터는 경로의 수를 간략하게 표시하기 위해서 수식을 하나 정해놓고 사용해보자.

F[A][B] = C 라는 수식을 지금부터 사용할 것인데, F[A][B] = C의 의미는 (A , B)까지 올 수 있는 경로의 수는 C개입니다. 를 의미한다. 즉, 만약, 모든 좌표에 대한 위의 수식값을 다 구했다면, 우리가 원하는 결과값은 F[N - 1][N - 1]에 저장되어 있을 것이다. 그럼 시작해보자.

가장 먼저 기본적으로 우리가 직접 세팅해줘야 하는 좌표가 하나 있다.

바로 (0 , 0)좌표이다. (0 , 0)좌표는 (0 , 0)으로 올 수 있는 어떠한 좌표도 없기 때문이다.

오른쪽 혹은 아래쪽으로만 움직일 수 있고, 오른쪽 혹은 아래쪽으로 움직여서 (0 , 0)으로 와야 한다면 그 좌표는

(-1 , 0) 이거나 (0 , -1) 이어야 하는데, 이러한 좌표는 존재하지 않기 때문에 직접 세팅해 주어야 한다.

그럼, (0 , 0)까지 올 수 있는 경로의 갯수는 1개라고 설정 후 진행해보자.

F[0][0] = 1

(0 , 0) 에서 움직일 수 있는 좌표를 확인해보자. (0 , 0) = 1 이라는 값을 가지고 있고, 이는 오른쪽 혹은 아래쪽으로 1칸 이동이 가능하다는 것을 의미한다.

따라서, (0 , 1)과 (1 , 0)으로 움직일 수가 있다.

그럼 (0 , 1)과 (1 , 0)으로 움직일 수 있는 경로의 수가 0개에서 1개로 갱신이 된다. 왜 ? (0 , 0)에서 (0 , 1)로 가면되고,

(0 , 0)에서 (1 , 0)으로 가면 되기 때문이다.

따라서, 우리는 F[1][0] = 1 , F[0][1] = 1 이라는 결과값을 얻게 된다.

위의 식을 수식을 이용해서 표현해본다면, F[1][0] = F[0][0] , F[0][1] = F[0][0] 이 된다고 표현할 수 있다.

그럼(0 , 1)로 가보자. (0 , 1)도 좌표가 '1'이고, 오른쪽과 아래쪽으로 1칸 이동이 가능하다.

그럼, (0 , 2)와 (1 , 1)로 이동하게 될 것이다. 마찬가지로, (0 , 2)와 (1 , 1)까지 올 수 있는 경로의 수가 갱신될 것이다.

바로, F[0][2] = F[0][1], F[1][1] = F[0][1]로 !

같은 방식으로 (0 , 2)를 진행하게 되면, F[1][2] = F[0][2]로 설정이 될 것이다.

그럼 ! 지금까지 구한 F[][]의 값을 정리해서 나타내보자.

아직 구하지 않은 값들에 대해서는 '-'로 표시하겠다.

.

지금까지 구한 F[][]의 결과값들이다. 우리는 (0 , 0) ~ (0 , 2)까지 탐색을 해봤고, 그 결과 위의 표와 같은 경로의 수를 얻었다. 그럼 계속해서 진행해보자.

이제 (1 , 0)의 좌표를 확인해보자. (1 , 0) = 2 라는 값을 가지고 있다. 즉 ! 2칸을 움직일 수 있다는 것인데, 이 때 만약 아래칸으로 점프를 한다면 ?? 맵의 범위를 벗어나기 때문에 올바르게 움직이는 상황이 아니게 된다.

따라서, (1 , 0)에서 오른쪽으로만 움직일 수 있다. (1 , 0)에서 오른쪽으로 2칸 움직여보니, (1 , 2)가 나오고, 마찬가지로 위에서 했던 방식대로 수식을 적어보면 F[1][2] = F[1][0]이 된다.

그런데 ! 이게 잘못되었다는 것이다. 왜 그럴까 ??

(1 , 2)라는 좌표에 주목해보자. 우리는 분명히, (0 , 2)에서 아래쪽으로 한 칸 움직이는 경로를 통해서 (1 , 2)로 갔었던 적이 있다. 즉 ! (0 , 2)에서 의해서 "(1 , 2)로 가는 경로의 수는 1개입니다." 라고 갱신이 되었다.

그런데 ! 지금보니, (1 , 0)에서도 (1 , 2)로 갈 수 있는 경로가 존재하는 것이다.

즉 ! F[1][2] = F[1][0]으로 나타내면, 결국 F[1][2] = 1이 될텐데, 정확한 F[1][2]의 값은 '2'라는 것이다.

우리가 지금까지 위에서 계산한 방식은 잘못되었다는 것이다.

(x , y)에서 (nx , ny)로 가는 상황을 생각해보자.

우리는 지금까지 F[nx][ny] = F[x][y] 의 꼴로 값을 갱신해 주었다. 그런데 이렇게 계산을 하게 되면, "기존에 한번도 와보지 못했던 좌표에 대해서는 상관이 없지만, 한번 이상 와봤던 좌표들에 대해서는 문제가 발생" 한다.

따라서, 정확한 계산을 하기 위해서는 F[nx][ny] = F[nx][ny] + F[x][y]의 형태로 계산해 주어야 한다는 것이다.

그럼 위와 같이 계산하지 않았는데도 (0 , 0) ~ (0 , 2)까지 탐색을 했을 때 제대로된 결과값이 나왔던 이유는 ? 바로 "기존에 한번도 와보지 못했던 좌표들만! 값이 갱신이 되었기 때문" 이다.

그럼 우리가 위에서 했던 과정들을 정리해보자. 위와 같은 방식이 계속해서 반복되기 때문에 (N - 1, N - 1)까지 해볼 필요는 없을 것 같다.

1. 현재 좌표가 가진 값을 확인한다. (값 = Value)

2. 현재 좌표에서 오른쪽, 아래쪽으로 +Value만큼 한 좌표가 맵의 범위 내에 있는지 확인한다.

3. +Value만큼 한 좌표(nx , ny)가 범위 내에 있다면, F[nx][ny] = F[nx][ny] + F[x][y] 로 경로의 수를

   갱신해준다.

4. 최종 결과값은 F[N - 1][N - 1]에 존재한다.

실제 코드에서는 F[][]의 역할을 할 수 있는 2차원 배열을 하나 선언해 주었다.(코드 : DP[][])

DP[][]의 의미는 F[][]의 의미와 같고, 모든 좌표에 대해서 위의 과정들을 반복해 주었다.

또한, 맵의 현재 좌표값이 '0'인 좌표에 대해서는 탐색이 필요하지 않다. 왜냐하면 어차피 움직이지 못하는 좌표이기 때문이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N;
int MAP[MAX][MAX];
long long DP[MAX][MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    DP[0][0] = 1;
    for (int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if (DP[i][j] == 0) continue;
            if (i == N - 1 && j == N - 1) continue;
 
            int Jump = MAP[i][j];
            if (i + Jump < N) DP[i + Jump][j] = DP[i + Jump][j] + DP[i][j];
            if (j + Jump < N) DP[i][j + Jump] = DP[i][j + Jump] + DP[i][j];
        }
    }
    cout << DP[N - 1][N - 1] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}