[백준 20928] 걷는 건 귀찮아 (C++)

20928번: 걷는 건 귀찮아

 

1. 현재 인력거에서 M까지 갈 수 있는지 확인한다. M까지 갈 수 있다면 결과 값을 최솟값으로 갱신한다.

 

2. 현재 인력거에서 갈 수 있는 인력거들을 모두 queue에 넣는다. 이때 가장 멀리있는 인력거 위치 이후부터 찾는다. 인력거를 찾게되면 그때마다 가장 멀리있는 인력거의 위치를 갱신해준다.

 

 

알고리즘 과정

입력

4 10

1 3 5 7

4 6 5 2

파란색 동그라미는 인력거의 위치를 의미한다.

파란색 동그라미 밑에 있는 초록색 숫자는 해당 인력거가 갈 수 있는 범위를 의미한다.

가장 멀리 있는 인력거의 위치(이하 idx)는 0으로 초기화 된다.

 

 

현재 idx가 0이므로 idx=1인 인력거부터 살펴본다.

idx=1인 인력거의 위치가 3이므로 현재 인력거가 방문할 수 있는 범위 이내이다.

따라서 다음 인력거를 queue에 추가한다.

 

마찬가지로 idx=2인 인력거도 queue에 추가하고, idx를 2로 갱신한다.

 

 

현재 idx=2이므로 idx=3인 인덱스에 방문할 수 있는지 살펴본다.

이때 방문 가능하므로 queue에 idx=3인 인력거를 추가한다.

 

 

현재 인력거에서 목적지인 10에 도달할 수 있기 때문에 최종 답을 갱신해준다.

현재 idx=3이므로 더이상 idx를 증가시킬 수 없다.(인력거는 4개이므로 인덱스는 3까지이다.)

따라서 다음 인력거(7번 위치)를 보면 최종 목적지에 도달할 수 없기 때문에 답을 갱신하지 못하고 종료된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
// N: location num, M: destination
int N, M;
 
// first: location, second: moveRange
vector<pii > rickshawLocation;
 
void input(){
    cin >> N >> M;
    int a, b;
    for(int i = 0; i < N; i++){
        cin >> a;
        rickshawLocation.push_back({a, 0});
    }
    for(int i = 0; i < N; i++){
        cin >> b;
        rickshawLocation[i].second = b;
    }
}
 
struct DB{
    pii locationrange;
    int transferCnt;
};
 
int minAnswer = INF;
 
void solve(){
    queue<DB> que;
    
    que.push({rickshawLocation[0], 0});
    bool visited[100001];
    memset(visited, 0, sizeof(visited));
    visited[0] = true;
    
    // 확인한 지점 중 가장 멀리있는 위치(인력거 인덱스)
    int idx = 0;
    
    while(!que.empty()){
        int now = que.front().locationrange.first;
        int range = que.front().locationrange.second;
        int tcnt = que.front().transferCnt;
        que.pop();
        
        if(M <= now + range){
            minAnswer = min(minAnswer, tcnt);
        }
        
        int tempidx = idx+1;
        while(tempidx < N){
            if(visited[tempidx]){
                tempidx++;
                continue;
            }
            int iscanreach = rickshawLocation[tempidx].first;
            if(iscanreach <= now + range){
                visited[tempidx] = true;
                que.push({rickshawLocation[tempidx], tcnt+1});
                idx = max(idx, tempidx);
            }
            else break;
            tempidx++;
        }
    }
}
 
int main(){
    input();
    solve();
    if(minAnswer == INF) cout << "-1";
    else cout << minAnswer;
    
    return 0;
}