백준 1890 C++ - 점프

Intro

문제해결 및 소스코드

• 먼저, DFS를 통해 해결해보려고 했다.

#include <iostream>
#include <queue>

using namespace std;

int n;						// 판의 크기(4~100 x 4~100)
int board[101][101];		// 게임판
int cnt;					// 목표지점에 도착한 경우의 갯수

void DFS(int x, int y)
{
	// 목적지 도착
	if (x == n && y == n)
	{
		cnt++;
		return;
	}

	int nx = x + board[x][y];
	int ny = y + board[x][y];
	
	// 1. 오른쪽으로 갈순있지만 아래쪽으로 못갈 때
	if (nx>n && ny<=n)
	{
		DFS(x, ny);
	}
	// 2. 오른쪽으로 갈순없지만 아래쪽으로 갈수 있을 때
	else if (nx <= n && ny > n)
	{
		DFS(nx, y);
	}
	// 3. 오른쪽으로도 갈 수 있고 아래쪽으로도 갈 수 있을 때
	else
	{
		DFS(nx, y);
		DFS(x, ny);
	}
}

int main()
{
	cin >> n;

	// 게임판 입력
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			cin >> board[i][j];
		}
	}

	DFS(1, 1);
	cout << cnt;
}

• (1,1)에서 시작하여, (n,n)에 도착한 경우에 카운트를 증가시켜 최종답을 출력하도록했다.
  • DFS에서는 발생할 수 있는 3가지 경우를 나누어 다음좌표에서 DFS를 호출하도록했다.
• 결과적으론, 시간초과가 발생했다.

따라서 다른방법을 찾아보기로했다.

• board는 예제로 주어진 게임판의 모습이고, dp는 게임판과 크기가같은 0으로초기화된 또다른 판이다.
• dp의 칸에 쓰여질 숫자는 해당 칸에 갈 수 있는 경로의 숫자이다.
  • 게임은 반드시 (1,1)에서 시작하므로 dp(1,1) = 1 로 설정한다.
  • (1,1)에서 오른쪽 또는 아래쪽으로 board(1,1)에 쓰여진 숫자만큼의 좌표로 점프할 수 있으므로
  • nx(다음x좌표) ny(다음y좌표)를 미리 계산하고, nx와 ny가 유효한 좌표인지 확인한다.
  • 만약 유효한 좌표라면 현재좌표로 올 수 있는 경우의수와 다음좌표로 갈 수 있는 경우의 수를 더해준다.
• 최종적으로 dp(n,n)을 출력한다.

#include <iostream>

using namespace std;

int n;
int board[101][101];
long long int dp[101][101];

int main()
{
	cin >> n;

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

	dp[1][1] = 1;

	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			// 목표칸일 때
			if (board[i][j] == 0)
				continue;

			// 점프가 가능한 곳일 때
			if (dp[i][j] != 0)
			{
				int nx = i + board[i][j];
				int ny = j + board[i][j];

				if (nx <= n) dp[nx][j] += dp[i][j];
				if (ny <= n) dp[i][ny] += dp[i][j];
			}
			
		}
	}

	cout << dp[n][n];
}