[알고스팟] 외발뛰기

링크: https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

---

 완전탐색은 문제의 한 조각을 풀고 나머지 문제의 처리를 재귀함수에 맡길 수 있다. 나아가 분할정복 알고리즘은 부분문제의 결과를 조합하여 원하는 답을 도출한다. 동적 계획법은 분할정복에서 한발 더 나아간다. 분할정복으로 접근가능한 어떤 문제들은 중복되는 부분문제(overwrapping subproblems)가 생긴다. 이 경우 따로 처리해주지 않으면 같은 계산을 여러번 반복하는 비효율이 발생하게 된다. 이를 해결하기 위해서 부분문제의 결과를 캐싱(caching)하는 것이 동적 계획법이며, 캐싱하는 행위를 메모이제이션(memoization)이라고도 부른다.

 이 문제 역시 부분문제의 조합으로 풀 수 있으나, 중복되는 부분이 발생한다. 각기 다른 발판에서 같은 발판에 도달할 수 있기 때문이다. 그러나 도달한 발판에서 갈 수 있는 경우의 수는 정해져있다. 만약 이전에 그 발판에 도달했을때 왼쪽 하단에 도달하지 못했다면, 다음에 그 발판에 도착했을 때로 마찬가지이다. 이렇듯 함수의 입력에 따라 결과가 일정한 함수를 참조 투명한 함수(referential transparency function)이라고 부른다. 참조 투명성은 메모이제이션의 필요조건이다.

 

<파이썬3 소스코드>

import sys

def jump(x, y, N):
    if not (x < N and y < N):
        return False
    if cache[x][y]:
        return False
    now = board[x][y]
    cache[x][y] = True
    if now == 0:
        return True
    return jump(x + now, y, N) or jump(x, y + now, N)

for _ in range(int(sys.stdin.readline())):
    length = int(sys.stdin.readline())
    board = []
    cache = [[False for _ in range(length)] for _ in range(length)]
    for _ in range(length):
        board.append(list(map(int, sys.stdin.readline().split())))
    print('YES' if jump(0, 0, length) else 'NO')

 위에서 볼 수 있다시피 동적 계획법으로 문제를 풀때 일정한 양식을 따르면 좋다. 최상단에는 기저 사례를 정의하고, 그 이후 캐싱결과와 비교하며, 마지막으로 아래에 정답에 접근하기 위한 근본적인 알고리즘을 작성할 수 있다.

 

<C++ 소스코드>

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

bool jump(int x, int y, int N, const std::vector<std::vector<int>>& board, std::vector<std::vector<bool>>& cache)
{
	if (x >= N || y >= N) return false;
	if (cache[x][y]) return false;

	int now = board[x][y];
	cache[x][y] = true;
	if (now == 0) return true;
	return jump(x, y + now, N, board, cache) || jump(x + now, y, N, board, cache);
}


int main(void)
{
	
	int numTestcase;
	scanf("%d", &numTestcase);
	for (int i = 0; i < numTestcase; i++)
	{
		int length;
		scanf("%d", &length);
		std::vector<std::vector<int>> board(length);
		std::vector<std::vector<bool>> cache(length);
		for (int i = 0; i < length; i++)
		{
			board[i] = std::vector<int>(length);
			cache[i] = std::vector<bool>(length);
			for (int j = 0; j < length; j++)
			{
				int tmp;
				scanf("%d", &tmp);
				board[i][j] = tmp;
				cache[i][j] = false;
			}
		}
		bool ret = jump(0, 0, length, board, cache);
		std::string result = (ret ? "YES" : "NO");
		std::cout << result << "\n";

		for (int i = 0; i < length; i++)
		{
			board[i].clear();
			cache[i].clear();
		}
		board.clear();
		cache.clear();
	}
	return 0;
}

 c++로 풀이 시 주의할 점은 전역변수로 선언되지 않은 board와 cache 변수를 참조체로 받고 있다는 점이다. 물론 전역변수였다고 해도 함수 내에서 직접 벡터의 원소를 수정하기 위해 참조체로 받는 것이 타당하다. 번외로 clear보다 swap함수를 쓰는 것이 메모리가 해당 시점에 깔끔하게 정리된다.