백준 32294 - 수열과 개구리 (C++)

문제

• 문제 링크

  
   BOJ 32294 - 수열과 개구리 
  

• 문제 요약

길이 $n$의 수열 $a, b$가 주어진다. 이때, 수열 위 개구리가 다음 규칙에 따라 행동한다.



개구리의 현재 위치를 $x(1 ≤ x ≤ n)$라고 할 때, $b_x$초 이후 $x - a_x$ 또는 $x + a_x$로 이동한다.


개구리의 위치 $x$에 대해 개구리가 수열 밖에 도달하는 최초의 시각을 $f(x)$라고 정의할 때, $f(1), f(2), ... , f(n)$의 값을 모두 구해보자.



• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ n ≤ 2 \times 10^5$

$1 ≤ a_i ≤ n$

$1 ≤ b_i ≤ 10^6$

알고리즘 분류

• 그래프 이론 (Graphs)
• 최단 경로 (Shortest Path)
• 다익스트라 ($Dijkstra)

풀이

수열의 각 지점 $1, 2, ... , n$을 정점으로 볼때 가상의 정점 $0$과 $n+1$을 추가로 두고 생각해 보자. $0$은 $x < 1$인 구간을 함축하며 $n+1$은 $x > n$인 구간을 함축한다.

이어서 간선을 역방향으로 추가함으로써 문제를 뒤집어 생각해보면, 문제 서술상 바깥으로 정의되는 정점 $0, n+1$에서 정점 $1, 2, ... , n$으로의 최단 경로를 개척하는 단순한 다익스트라 문제로 변형하여 풀어낼 수 있다.

자세한 흐름은 아래 첨부된 코드를 참고하자.

전체 코드

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
 
    vector <int> a(n + 2), b(n + 2);
    for(int i(1); i <= n; i++) cin >> a[i];
    for(int i(1); i <= n; i++) cin >> b[i];
 
    vector <vector <pair<int, int>>> Gr(n + 2);
    for(int i(1); i <= n; i++)
    {
        Gr[min(i + a[i], n + 1)].emplace_back(i, b[i]);
        Gr[max(i - a[i], 0)].emplace_back(i, b[i]);
    }
 
    priority_queue <pair<ll, int>> pq;
    vector <ll> dist(n + 2, 2e18);
 
    pq.push({0, 0}), pq.push({0, n + 1});
    dist[0] = dist[n + 1] = 0;
 
    while(pq.size())
    {
        auto [cost, now](pq.top()); pq.pop();
        if(dist[now] < (cost *= -1))
            continue;
        for(auto [nxt, weight] : Gr[now])
        {
            ll cur(cost + weight);
            if(dist[nxt] > cur)
                pq.push({-(dist[nxt] = cur), nxt});
        }
    }
 
    for(int i(1); i <= n; i++)
        cout << dist[i] << ' ';
}

comment

끝