백준 1890 : 점프

1. 문제 : https://www.acmicpc.net/problem/1890

1890번: 점프

 

2. 문제 접근

• BFS : 다음 노드로 탐색할 수 있는 방법은 두 가지이므로 자식이 2개인 트리를 탐색하는 문제로 치환할 수 있다. 다만, 최악의 경우(모든 노드의 값이 1일 때), 시작점에서 사각형의 절반만 탐색하더라도 $2^N$개의 노드를 탐색해야 한다. 4 bytes * $2^N$만 해도 메모리가 터지는 것을 확인할 수 있다.
• DP : BFS에서 메모리 초과가 나는 이유는 방문했던 노드를 중복해서 계속 방문하기 때문에 중복되는 Sub-Tree가 너무 많기 때문이다. 이를 방지하기 위해 해당 노드를 방문하는 경우의 수를 저장한다면 중복 방문하는 노드를 제거하여 많은 메모리를 아낄 수 있다. (메모이제이션)

 

3. 문제 해결

1. 모든 좌표의 경로의 수를 0으로 초기화한다.
2. 모든 좌표를 순회하며 $(i, j)$ 좌표의 값이 0일 경우, 더 이상 움직일 수 없으므로 건너뛴다.
3. $(i, j)$ 좌표의 값이 0이 아닐 경우, 이동한 위치가 범위를 벗어나지 않는다면, 이동한 위치까지의 경로의 수에 $(i, j)$ 좌표까지의 경로의 수를 더한다.
4. 모든 좌표를 순회한 뒤 마지막 지점의 값을 반환한다.

DP[i + Dist][j] += DP[i][j];
DP[i][j + Dist] += DP[i][j];

 

4. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

long solution(int N, vector<vector<int>>& map)
{
	vector<vector<long>> dp;

	// Initialize the dp matrix
	for (int i = 0; i < N; i++)
	{
		vector<long> temp;

		for (int j = 0; j < N; j++)
		{
			temp.push_back(0);
		}

		dp.push_back(temp);
	}

	// Initialize the value
	dp[0][0] = 1;

	// Calculate the number of the path
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (dp[i][j] == 0) continue;
			if (map[i][j] == 0) continue;

			int dist = map[i][j];

			if (i + dist < N) // if the next point is in range
			{
				dp[i + dist][j] += dp[i][j];
			}
			if (j + dist < N) // if the next point is in range
			{
				dp[i][j + dist] += dp[i][j];
			}
		}
	}

	return dp[N - 1][N - 1];
}

int main()
{
	int N;
	vector<vector<int>> map;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		vector<int> temp;

		for (int j = 0; j < N; j++)
		{
			int value;
			cin >> value;
			temp.push_back(value);
		}

		map.push_back(temp);
	}

	cout << solution(N, map);

	return 0;
}