https://www.acmicpc.net/problem/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;
}
'백준' 카테고리의 다른 글
[백준/c++] BOJ 21278 - 호석이 두 마리 치킨 (1) | 2023.10.19 |
---|---|
[백준/c++] BOJ 16208 - 귀찮음 (0) | 2023.10.12 |
[백준/c++] BOJ 25214 - 크림 파스타 (0) | 2023.10.12 |
[백준/c++] BOJ 5558 - チーズ (Cheese) (0) | 2023.10.12 |
[백준/c++] BOJ 14496 - 그대, 그머가 되어 (0) | 2023.10.05 |