[BOJ/Silver 2] 백준 11060 점프 점프(C++)

문제 링크

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

11060번: 점프 점프

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1

10
1 2 0 1 3 2 1 5 4 2

예제 출력 1

5

알고리즘 분류

• 그래프 탐색

풀이

0번부터 시작해서 BFS를 이용하여 0~A[i]번째 칸만큼 오른쪽으로 이동한다.

N-1번째에 도착하거나 넘어갔을 때의 최소 이동 횟수를 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1005
#define LL long long
#define INF 2e9

using namespace std;
int N;
int A[MAX];
bool visited[MAX];
int answer = INF;

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

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurCnt = Q.front().second;
		Q.pop();

		if (CurX >= (N - 1)) {
			answer = min(answer, CurCnt);
			return;
		}
		for (int i = 0; i <= A[CurX]; i++) {
			if (!visited[CurX + i]) {
				visited[CurX + i] = true;
				Q.push(make_pair(CurX + i, CurCnt + 1));
			}
		}
	};
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	BFS(0);
	if (answer == INF) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << "\n";
	}

	return 0;
}