1326번: 폴짝폴짝

1326번: 폴짝폴짝

사용 언어: C++

문제 요약

개구리가 일렬로 놓여 있는 검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오. 

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

풀이

이 문제는 각 징검다리를 정점으로, 가능한 점프를 간선으로 하는 그래프에서 최단 경로를 찾는 문제와 같다. 일단 각 징검다리까지의 최소 점프 횟루를 저장할 배열 dp를 쓰고, 방문하지 않았다는 의미에서 전부 -1로 초기화.

모든 간선의 가중치 (점프 1회)가 1로 같아서 BFS를 쓰는 게 효율적이다.

그래서 시작점 dp[a]를 기준으로 queue에 넣고 갈 수 있는 곳들은 queue에 넣고, dp 값을 갱신한다. 

여기서 신경써야 할 것은 개구리는 앞뒤로 다 갈 수 있다는 것이다.

또한, 한번 방문해서 dp 값을 갱신한 곳은 이미 최적의 해가 되므로 더 이상 신경쓸 필요가 없어지게 된다. 그러므로 이렇게 채우다가 결국 dp[b] 값이 갱신이되면 스탑하고 출력하면 된다.

답

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    vector<int> Frog(N+1, 0);
    for(int i=1; i<=N; i++) cin >> Frog[i];
    
    int a, b;
    cin >> a >> b;
    
    vector<int> dp(N+1, -1);
    
    // 방문할 징검다리를 담을 큐
    queue<int> q;
    
    dp[a] = 0;
    q.push(a);
    
    while(!q.empty())
    {
        int current_pos = q.front();
        q.pop();
        
        if(current_pos == b) break;
        
        int jump_power = Frog[current_pos];
        
        // 앞으로 점프하는 경우
        for(int next_pos = current_pos + jump_power; next_pos <= N; next_pos += jump_power)
        {
            // 방문한 적이 없다면 업데이트
            if(dp[next_pos] == -1)
            {
                dp[next_pos] = dp[current_pos] + 1;
                q.push(next_pos);
            }
        }
        
        // 뒤로 점프
        for(int next_pos = current_pos - jump_power; next_pos >= 1; next_pos -= jump_power)
        {
            if(dp[next_pos] == -1)
            {
                dp[next_pos] = dp[current_pos] + 1;
                q.push(next_pos);
            }
        }
    }
    
    cout << dp[b] << '\n';

    return 0;
}