[종만북 문제] 외발 뛰기 (문제 ID : JUMPGAME, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. DP 문제를 풀 떄는, 먼저 완전 탐색으로 풀 수 있는지 체크를 해 보고, 메모이재이션이 가능한지를 파악하는 것도 좋은 접근 방법이다.

---

[종만북 문제] 외발 뛰기 (문제 ID : JUMPGAME, 난이도 : 하)

바로.. 예제 코드로 들어가 보자.

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

/****************************************************************************************************/

int N;
int arr[100][100];
bool visited[100][100];
int dir[2][2] = { {0, 1}, {1, 0} };

void sol()
{
	visited[0][0] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));

	while (!q.empty())
	{
		int i = q.front().first;
		int j = q.front().second;
		q.pop();

		for (int d = 0; d < 2; ++d)
		{
			int i2 = i + dir[d][0] * arr[i][j];
			int j2 = j + dir[d][1] * arr[i][j];

			if (i2 >= N || j2 >= N)
				continue;

			if (i2 == N - 1 && j2 == N - 1)
			{
				cout << "YES" << endl;
				return;
			}

			if (!visited[i2][j2])
			{
				visited[i2][j2] = true;
				q.push(make_pair(i2, j2));
			}
		}
	}
	
	cout << "NO" << endl;
}

void inputHandler()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> arr[i][j];
			visited[i][j] = false;
		}
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

핵심은, 이미 방문한 곳은 더 체크하지 않는 것이다! 

 

일단 DP 를 풀 때는, 재귀적으로 해결할 수 있는지를 체크하는 것부터 시작하는 것도 좋은 접근 방법이다.

 

책은 조금 더 깔끔한 풀이를 제공한다.