[백준/c++] BOJ 1326 - 폴짝폴짝

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

1326번: 폴짝폴짝

 

문제 설명

일렬로 놓여 있는 징검다리 사이를 뛰어다닌다. 징검다리에는 숫자가 각각 쓰여 있는데, 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다. a번째 징검다리에서 b번째 징검다리까지 가려고 할 때, 최소 몇 번 점프하여 갈 수 있는지 구한다.

 

징검다리의 개수 N (1 <= N <= 10,000)

a, b (1 <= a, b <= 10,000)

해결

bfs문제이다. 다른 문제들과의 차이점은 배수만큼 이동할 수 있다는 것이다.

bfs 함수 내부에서 이동할 때, 징검다리에 적힌 숫자만큼 오른쪽, 왼쪽으로 이동하면 된다.

오른쪽으로 이동할 때는 징검다리의 크기를 넘어가지 않을 때까지 증가시키고, 왼쪽으로 이동할 때는 0을 넘어가지 않을 때까지 징검다리 숫자만큼 감소시키면 된다.

 

왼쪽으로도 이동할 수 있다는 게 포인트다.

코드

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

int n;
int board[10002];
int a, b;
int visited[10002];

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

	while (!q.empty()) {
		auto cur = q.front(); q.pop();

		for (int i = cur + board[cur]; i < n; i += board[cur]) {
			if (visited[i]) continue;
			if (i == b) return visited[cur];
			visited[i] = visited[cur] + 1;
			q.push(i);
		}
		for (int i = cur - board[cur]; i >= 0; i -= board[cur]) {
			if (visited[i]) continue;
			if (i == b) return visited[cur];
			visited[i] = visited[cur] + 1;
			q.push(i);
		}
	}
	return -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 >> a >> b;
	a--; b--;

	cout << bfs();
}