[백준/c++] BOJ 14248 - 점프 점프

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

14248번: 점프 점프

 

문제 설명

영우는 n개의 돌이 놓여 있는 돌다리 위에 있다. 돌다리의 돌에는 숫자 Ai가 하나씩 적혀 있는데, 이 적혀 있는 숫자만큼 왼쪽이나 오른쪽으로 점프할 수 있다. 이때, 돌다리 밖으로 나갈 수는다.

출발점 s에서 출발할 때, 방문 가능한 돌들의 개수를 구한다.

n (1 <= n <= 100,000)

Ai (1 <= Ai <= 100,000)

s (1 <= s <= n)

 

해결

간단한 2차원 bfs 문제이다.

 

출발점을 queue 안에 넣어 시작하게 하였고, visited 하지 않은 지점에 도착하면 ans를 증가하고 다시 queue 안에 넣어 주는 방식으로 구현하였다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int board[100001];
int ans = 1, visited[100001];

int range_over(int nx) {
	return nx < 0 || nx >= n;
}

void bfs() {
	m--;
	queue<int> q;
	q.push(m);
	visited[m] = 1;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int a : {cur + board[cur], cur - board[cur]}) {
			if (range_over(a) || visited[a]) continue;
			ans++;
			q.push(a);
			visited[a] = 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> board[i];

	cin >> m;

	bfs();
	cout << ans;

}