백준 11060 - 점프 점프(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11060

11060번: 점프 점프

BFS문제입니다.

1번점에서 시작했을때, N번점까지 갈 수 있는지를 확인하는 문제입니다.

저는 배열을 이용해 X번점에 도달할 수 있는 최소 점프 수를 저장했습니다.

 

먼저 해당 배열에 INF 값을 저장했습니다. 탐색이 끝났는데도 N번칸의 배열 값이 INF라면 -1을 출력하면 되며, INF 값이 아니라면 해당 칸의 값을 출력해주면 됩니다.

 

X번칸에서의 탐색 범위는 해당 칸에서 뛸 수 있는 범위입니다.

예를 들어 X번 칸에서 5칸을 뛸 수 있다면, X + 1 ~ X + 5 까지의 위치가 탐색 범위가 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

int N;
int map[1001];
int dp[1001];

void bfs(int start) {
	queue<pair<int, int>> q;
	dp[start] = 0;
	q.push({start,0});
	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (x == N) {
			dp[N] = min(dp[N], cnt);
		}
		for (int i = 1; i <= map[x]; i++) {
			int xx = x + i;
			if (xx > N) break;
			if (dp[xx] == INF || dp[xx] > cnt + 1) {
				dp[xx] = cnt + 1;
				q.push({ xx , cnt + 1 });
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= N; i++) dp[i] = INF;
	bfs(1);
	if (dp[N] == INF) cout << "-1";
	else cout << dp[N];
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> map[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요