점프 (feat. 백준, 2253번)

점프
https://www.acmicpc.net/problem/2253

2253번: 점프

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, ans = 99999999;
    bool rock[10001]{false};
    vector<int> check[10001];
    cin >> N >> M;
    for(register int m = 0, v; m < M; ++m)
        cin >> v, rock[v] = true;
    queue<tuple<int, int, int>> q;      // 위치, 가속, 횟수
    q.push(make_tuple(1, 0, 0));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        auto v = get<0>(p), s = get<1>(p), cnt = get<2>(p);
        if(v > N)
            continue;
        else if(v == N){
            ans = min(ans, cnt);
            continue;
        }
        else{
            register int jump[] = {s - 1, s, s + 1}, nv, nc = cnt + 1;
            for(register int i = 0; i < 3; ++i)
                if(jump[i] > 0){
                    nv = v + jump[i];
                    if(nv <= N && !rock[nv] && find(check[nv].begin(), check[nv].end(), jump[i]) == check[nv].end())
                        check[nv].push_back(jump[i]), q.push(make_tuple(nv, jump[i], nc));
                }
        }
    }
    if(ans == 99999999)
        cout << -1;
    else
        cout << ans;
    return 0;
}
// *&)*@*

 

반응형

1. 현재 위치에서 이동할 수 있는 조건은 이전 속도 - 1, 이전 속도, 이전 속도 + 1 만큼만 존재합니다.
2. 또한 특정한 위치에 도달했을때, 이곳으로 오기 위했던 속도가 이미 있다면 (체크 요소) 재방문할 필요가 없습니다.
   즉, 10이라는 위치에 2라는 속도로 왔다면, 이전에 2라는 속도로 왔던 적이 없는 경우에만 방문합니다.
3. 따라서 이와 같은 조건으로 bfs를 수행하면 됩니다.