문제

출처 : https://www.algospot.com/judge/problem/read/JUMPGAME

땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.

균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.

게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

출력

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 “YES”를, 아닐 경우 “NO”를 출력합니다. (따옴표 제외)

풀이

동적 계획법은 앞서 학습한 재귀함수에서 풀이를 반복할 때, 이전에 계산하였던 답을 저장하고 다음 계산 시 해당 부분문제를 사용할 때 저장하였던 답을 호출하여 효율적으로 문제를 풀이하는 접근 방식이다. 이 때 중요한 개념이 메모이제이션(memoization)으로, 기존에 계산한 값을 저장하였다가 재활횽하는 기법을 의미한다. 이 메모이제이션을 적절히 활용하여 문제를 푸는 것이 동적 계획법의 핵심이라고 볼 수 있다.

static void jump(int a, int b) {
		int n = A.length;
		int move = A[a][b];
		int down = a + move;
		int right = b + move;
		if (down < n) {
			if (cache[down][b] != 1) {
				cache[down][b] = 1;
				jump(down, b);
			}
		}
		if (right < n) {
			if (cache[a][right] != 1) {
				cache[a][right] = 1;
				jump(a, right);
			}
		}

	}

입력값으로 받은 전역 배열 A의 배열의 인덱스 a,b 에서 해당 값 만큼 오른쪽이나 아래로 점프하도록 구현한 함수이다. 핵심은 메모이제이션을 구현할 전역 배열 cache를 설정하고, 게임판 인덱스의 해당 값만큼 다음 위치로 이동할 때, 해당 인덱스의 cache값을 1로 설정하여 이동가능 여부를 저장하여 재활용하는 것이다. 이동 전에, 해당 인덱스가 배열 범위를 벗어나는지 검사하며 해당 범위로 이동함으로써 cache 배열의 값을 채워나간다.

따라서 최종적으로 구해야 할 게임판의 끝부분 인덱스인 cache[n-1, n-1]에 저장된 값을 확인하여 해당 위치로 이동이 가능한지 판별할 수 있다.