BaekJoon 11060번: 점프 점프(C++)

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) i번째 index에 있는 값 이하로 점프할 수 있기에 for문을 1부터 arr[index]까지 값으로 돌려 모든 경우의 수를 bfs 기반의 알고리즘으로 탐색하여 문제를 해결하였다.

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;

int n;
int arr[1001];
bool visited[1001];
void bfs(int start)
{
	queue<pair<int, int>> q;
	visited[1] = true;
	q.push({ 1,0 });
	while (!q.empty())
	{
		int nowIndex = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (nowIndex == n)
		{
			cout << cnt;
			return;
		}
		for (int i = 1; i <= arr[nowIndex]; i++)
		{
			if (!visited[nowIndex+i]&& nowIndex+i<=n)
			{
				visited[nowIndex+i] = true;
				q.push({ nowIndex+i,cnt + 1 });
			}
		}

	}
	cout << -1;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	bfs(1);
}