알고스팟 알고리즘: 외발 뛰기(JUMPGAME) [C++]

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

algospot.com :: JUMPGAME

1. 코드

#include <iostream>
#include <vector>

using namespace std;

int N;		//크기
bool flag;	//정답 확인
void solution(vector <vector <int>> g, vector <vector <int>> &c, int x, int y)
{
	if (c[y][x] == 1) return;	//이미 탐색한 구역이라면
	if (flag == true) return;	//정답을 이미 확인했다면
	if (x == N - 1 && y == N - 1) flag = true;
	if (x + g[y][x] < N) solution(g, c, x + g[y][x], y);	//오른쪽 탐색
	if (y + g[y][x] < N) solution(g, c, x, y + g[y][x]);	//아래쪽 탐색
	c[y][x] = 1;	//오른쪽과 아래쪽을 탐색이 끝났다면
}

int main(void)
{
	int C;
	cin >> C;

	while (C--)
	{
		cin >> N;
		vector <vector <int>> ground;
		vector <vector <int>> cache(N, vector<int>(N, 0));
		for (int i = 0; i < N; i++)
		{
			vector <int> line;
			for (int j = 0; j < N; j++)
			{
				int temp;
				cin >> temp;
				line.push_back(temp);
			}
			ground.push_back(line);
		}
		flag = false;
		solution(ground, cache, 0, 0);
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

(실행)

2. 풀이

cin >> N;
vector <vector <int>> ground;
vector <vector <int>> cache(N, vector<int>(N, 0));
for (int i = 0; i < N; i++)
{
	vector <int> line;
	for (int j = 0; j < N; j++)
	{
		int temp;
		cin >> temp;
		line.push_back(temp);
	}
	ground.push_back(line);
}

먼저 땅따먹기에 사용되는 크기(N)를 정해주고 그리고 2차원 벡터를 이용하여 땅따먹기의 수를 적을 ground와 메모이제이션을 위한 cache를 만들어주는데 cache같은 경우 N*N 크기에서 모든 값을 0으로 초기화 해줍니다. 그리고 반복문을 통해서 값을 입력 후 2차원 벡터에 저장해줍니다.

flag = false;
solution(ground, cache, 0, 0);
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;

그리고 매번 flag에 false로 설정을 한 뒤 solution이라는 함수를 실행한 후 flag의 값이 true라면 YES를 출력하고 아니라면 NO를 출력합니다.

void solution(vector <vector <int>> g, vector <vector <int>> &c, int x, int y)
{
	if (c[y][x] == 1) return;	//이미 탐색한 구역이라면
	if (flag == true) return;	//정답을 이미 확인했다면
	if (x == N - 1 && y == N - 1) flag = true;
	if (x + g[y][x] < N) solution(g, c, x + g[y][x], y);	//오른쪽 탐색
	if (y + g[y][x] < N) solution(g, c, x, y + g[y][x]);	//아래쪽 탐색
	c[y][x] = 1;	//오른쪽과 아래쪽을 탐색이 끝났다면
}

이 문제는 오른쪽과 아래쪽만으로 진행됩니다. 하지만 크기를 넘어서면 안됩니다. 그렇기에 계산결과 땅의 크기보다 작다면 진행이 됩니다. 먼저 오른쪽으로 탐색 후 아래쪽을 탐색을 합니다. 어느 지점의 오른쪽과 아래쪽이 탐색이 끝났다면 그 지점에서는 도착점에 도달할 수 없기에 이미 이곳에 대한 탐색은 이미 끝났다는 의미로 cache 벡터인 c 벡터에 1로 표시를 해줍니다. 그리고 탐색이 전부 완료된다면 flag 값에 true를 반환합니다.

그리고 진행이 될 때 해당 지점의 탐색을 이미 완료했다면(c 벡터가 1이라면) 해당 함수를 탐색할 이유가 없기에 종료하고 마찬가지로 이미 도착지점에 도달된 것이 확인이 되었다면(flag가 true라면) 더이상 탐색할 이유가 없기에 함수를 종료해줍니다.

3. 느낀 점

아직 동적 계획법에 대해서 능숙하지는 않지만 이번 문제를 통해서 생각보다 어렵지 않아서 자신감을 가지고 도전해보아야겠다.