[BaekJoon/백준] 11060번 점프 점프

 

 

이 문제도 BFS로 해결하는 대표 유형적인 문제였다!

 

99%에서 틀릴 수가 있는데, 주의할 점은

 

입력이 아래와 같을 때

1
0

-1이 아니라 0이 나와야하는게 맞다.

 

나 같은 경우 맨 아래 줄을 

    cout << ((DEPTH_COUNT[N - 1] == 0) ? -1 : DEPTH_COUNT[N - 1]) << "\n";

로 했다가, 틀렸고

    cout << (!(VISIT[N - 1]) ? -1 : DEPTH_COUNT[N - 1]) << "\n";

로 고쳐서 해결했다.

 

 

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

using namespace std;

int N;

int MAP[1000]; // 0 ~ 999 맵
bool VISIT[1000];
int DEPTH_COUNT[1000];


void bfs(int pos) {
    
    
    queue<int> que;
    
    que.push(pos); // 현재 위치
    VISIT[pos] = true;
    
    
    while(!que.empty()) {
        
        int P = que.front(); // 위치
        int L = MAP[P]; // 해당 위치에서 최대로 갈 수 있는 값
        
        que.pop();
        
        // 1 ~ x 까지 ( 0은 어차피 제자리니까 해줄 필요 없 )
        for(int i = 1; i <= L; i++) {
            
            int NEW_P = P + i;
            
            if(NEW_P > N - 1)
                continue;
            
            if(!VISIT[NEW_P]) {
                
                que.push(NEW_P);
                VISIT[NEW_P] = true;
                
                DEPTH_COUNT[NEW_P] = DEPTH_COUNT[P] + 1;
            }
        }
    }
}

int main() {
    
    
    cin >> N;
    
    
    for(int i = 0; i < N; i++)
        cin >> MAP[i];
    
    
    bfs(0);
    
    
    cout << (!(VISIT[N - 1]) ? -1 : DEPTH_COUNT[N - 1]) << "\n";
    
}

 

 

소요시간 : 20분