[BOJ] 11060번_점프 점프_BFS (C++)

[문제]

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

1xN 크기의 미로가 있다. 이 미로의 각 칸에는 정수가 하나 쓰여 있는데, 쓰여진 정수이하 만큼 오른쪽 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어 3번째 칸에 3이 쓰여있으면 4,5,6번 칸 중 하나로 점프할 수 있다.

지금 미로의 가장 왼쪽 끝에 갇혀있을 때, 최소 몇 번 점프해야 오른쪽 끝으로 갈 수 있는 지 구하는 프로그램을 만드는 문제이다. 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력하면 된다.

[사용 알고리즘]

BFS(너비 우선 탐색)

[풀이 핵심]

• 1번칸(가장 왼쪽)부터 BFS를 통해 탐색하면 된다. queue에 현재 노드 index와 현재 몇 번 점프했는지 저장해가며 탐색하면 N에 도착했을 때, count가 정답이다.
• 만약 N번째 칸(미로의 오른쪽 끝)에 도착하지 못했으면(!visited[N]인 경우), 가장 오른쪽 끝으로 갈 수 없는 경우라고 판단하고 -1을 출력하면된다.
• 현재 칸에서 점프할 수 있는 칸을 전부 탐색해도 어차피 v == N일때, 답을 출력하고 프로그램을 종료하기 때문에, 최소 점프 횟수에 너무 신경쓰지 않아도 된다.

[코드]

//boj11060번_점프 점프_그래프

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int graph[1001];
bool visited[1001];

int N;

void BFS() {
	visited[1] = true;

	queue<pair<int, int>> q;
	q.push({ 1,0 });

	while (!q.empty()) {
		int v = q.front().first;
		int count = q.front().second;
		q.pop();

		if (v == N) {
			cout << count;
			exit(0);
		}

		for (int i = 1; i <= graph[v]; i++) {
			if (!visited[v + i]) {
				visited[v + i] = true;
				q.push({ v + i,count + 1 });
			}
		}
	}
	if (!visited[N]) {
		cout << -1;
		exit(0);
	}
}

int main() {
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> graph[i];
	}

	BFS();

	return 0;
}