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

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

1890번: 점프

 

두 개의 배열을 사용해서 풀었다.

 

1. int m[100][100]
이동배열
문제의 입력값을 저장한다. map[1][2]는 1행, 2열에서 오른쪽, 아래로 이동 가능한 칸 수다.

2. long visit[100][100]
도달 가능 경로 배열
 visit[3][4]의 값은 3행 4열로 도달할 수 있는 경우의 수를 뜻한다.
만약에 값이 0이면 아직 한 번도 방문하지 않았다는 뜻이다. 

 

그냥 모든 칸에서 오른쪽, 왼쪽을 검사해서 이동 위치값을 아직 방문 안했으면 자기 자신을 넣어주고, 방문 했으면 이동 위치값에 자기 자신을 더해주면 된다. 

 

단, 행과 열이 가장 마지막에 도달하면 break 해준다. 목표지점이기 때문이다. 

 

#include <iostream>
using namespace std;

int m[100][100]; // 이동 배열
long visit[100][100]; // 자료형 주의
int n;

int main() {

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];

	visit[0][0] = 1;
	int row, col;

	// 한 칸씩 오, 왼 검사. 방문 안했으면 자기 자신 넣어주고, 방문 했으면 더해줌
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == n - 1 && j == n - 1) break;

			// 오른쪽 이동
			col = j + m[i][j];
			if (col < n) {
				if (!visit[i][col]) visit[i][col] = visit[i][j];
				else visit[i][col] += visit[i][j];
			}

			// 아래 이동
			row = i + m[i][j];
			if (row < n) {
				if (!visit[row][j]) visit[row][j] = visit[i][j];
				else visit[row][j] += visit[i][j];
			}	
		}
	}

	cout << visit[n - 1][n - 1];

	return 0;
}