[baekjoon 1326] 폴짝폴짝 (BFS) (C++)

www.acmicpc.net/problem/1326

1326번: 폴짝폴짝

문제는 개구리가 징검다리를 뛰어다니는데, 그 징검다리에는 각각 숫자가 써져있고 개구리는 자신이 서있는 징검다리의 숫자의 배수만큼 점프할 수 있다.

즉, 10개의 징검다리에서 1 2 3 4 5 6 7 8 9 1 이 써져있고 2번에서 9번까지 가고 싶다면

처음 징검다리 2번의 경우 : 2가 써져있으므로 2의 배수인 4 6 8 10을 각각 한 번의 점프로 방문이 가능하다.

그 이후 10의 경우 : 1이 써져있으므로 앞 또는 뒤로 1의 배수만큼 움직일 수 있다. 즉, 방문하지 않은 9 7 5 3 1을 각각 한 번의 점프로 방문이 가능하다.

따라서 2번에서 9번은 2 -> 10 -> 9로 총 두 번만에 방문이 가능하다.

 

처음에 뒤로 점프하는 경우는 생각하지 않아서 틀렸다.

 

최소 몇 번 점프를 해서 목적지에 도착할 수 있는가를 물어보기에 최단 거리를 찾는 BFS를 이용했다.

BFS를 수행해주면서 방문한 곳에 더 최단거리로 도착할 수 있는 경우의 수가 있지 않을까 생각을 했지만

나중에 그런 경우를 찾아서 방문한다는 것은 이미 전에 방문했던 수보다 업데이트되어서 방문했을 것이다. 즉, 제일 먼저 방문해서 체크하는 경우가 가장 최소다.

 

나머지는 기본 BFS 풀듯이 방문 체크해주면서 각각 배수만큼 탐색해주면 된다.

 

#include <iostream>
#include <queue>

using namespace std;

int N, num, from, to, road[10001], check[10001], record[10001];

void BFS(int from, int to) {
	queue<int> q;
	q.push(from);
	check[from] = true;

	while (!q.empty()) {
		int temp = q.front();
		q.pop();

		if (temp == to) {
			return;
		}

		for (int i = temp + road[temp]; i <= N; i += road[temp]) {
			if (!check[i]) {
				record[i] = record[temp] + 1;
				q.push(i);
				check[i] = true;
			}
		}
		for (int i = temp - road[temp]; i >=1; i -= road[temp]) {
			if (!check[i]) {
				record[i] = record[temp] + 1;
				q.push(i);
				check[i] = true;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> road[i];
	}
	cin >> from >> to;
	if (from == to) {
		cout << "0";
		return 0;
	}
	BFS(from, to);

	if (record[to] == 0) {
		cout << -1;
	}
	else
		cout << record[to];
}