[알고리즘 문제해결 전략] 외발 뛰기 문제

문제출처

• [알고리즘 문제해결 전략1] - 8장 동적 계획법 예제
• 소스코드는 구현한 함수의 동작 여부를 관찰하기 위해 본인의 테스트 코드를 추가하여 작성한 결과이다.

문제 설명

• N x N 크기의 격자에 1부터 9까지의 정수가 적힌 게임판이 있다.
• 게임의 목적은 왼쪽 위 칸(0,0)에서 시작해서 게임판의 맨 오른쪽 아래 칸(N-1, N-1)에 도달하는 것이다.
• 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있다.
• 시작점에서 끝점으로 도달하는 방법이 존재하는지 확인한다.

문제 접근 방향1 (재귀 호출을 통한 완전 탐색)

• 시작점에서 갈 수 있는 모든 경우의 수를 찾아보고, 끝점에 도달할 수 있는지 확인하는 방법
• 도달할 수 있는 경로를 하나만 찾으면 되지만, 최악의 경우 모든 경우의 수를 따져봐야 하는데 n이 100만 넘어가도 시간 초과에 걸릴 수 있다.

구현 (재귀 호출을 통한 완전 탐색)

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

bool jump(vector<vector<int>>& board, int n, int xpos, int ypos) {
	// 기저사례: 범위를 벗어난 경우
	if (xpos >= n || ypos >= n) return false;
	// 기저사례: 마지막 칸에 도달한 경우
	if (xpos == n - 1 && ypos == n - 1) return true;

	return jump(board, n, xpos + board[xpos][ypos], ypos) || jump(board, n, xpos, ypos + board[xpos][ypos]);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> board(n, vector<int>(n, 0));
	for (int r = 0; r < n; r++) 
		for (int c = 0; c < n; c++) 
			cin >> board[r][c];

	if (jump(board, n, 0, 0))
		cout << "Possible\n";
	else
		cout << "Impossible\n";

	return 0;
}

문제 접근 방향2(메모이제이션)

• 메모이제이션 기법을 통해 이미 도달한 곳에 대한 중복 호출을 줄인다.

구현(메모이제이션)

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

int jump(vector<vector<int>>& cache, vector<vector<int>>& board, int n, int xpos, int ypos) {
	// 기저사례: 범위를 벗어난 경우
	if (xpos >= n || ypos >= n) return 0;
	// 기저사례: 마지막 칸에 도달한 경우
	if (xpos == n - 1 && ypos == n - 1) return 1;
	int& ret = cache[xpos][ypos];
	if (ret != -1) return ret;

	return ret = jump(cache, board, n, xpos + board[xpos][ypos], ypos) || jump(cache, board, n, xpos, ypos + board[xpos][ypos]);
}

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> board(n, vector<int>(n, 0));
	vector<vector<int>> cache(n, vector<int>(n, -1));
	for (int r = 0; r < n; r++) 
		for (int c = 0; c < n; c++) 
			cin >> board[r][c];

	if (jump(cache, board, n, 0, 0))
		cout << "Possible\n";
	else
		cout << "Impossible\n";

	return 0;
}

Test Case

# 입력
<TC1>
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 1

<TC2>
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 3
3 3 1 2 3 4 1
1 5 2 9 4 7 1

# 출력
<TC1>
Possible

<TC2>
Impossible