[ baekjoon ] #11060 점프 점프

eunheelog·2023년 6월 1일

baekjoon

목록 보기

2/20

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

💡 Idea - BFS

1*N크기의 vector <int> jump(N); 생성
점프할 수 있는 크기를 jump[i]로 입력 받기
시작 위치를 저장하기 위한 queue 와 점프 횟수를 저장하기 위한 dp생성
처음 위치인 0을 queue에 push한 후 비어있을 동안 아래 과정을 반복
→ 현재위치 queue.top() 에서 점프할 수 있는 경우의 수 생각해보기
→ 현재위치에 점프 크기 0 ~ jump[i]를 더해보며 N보다 작을 경우,

dp[점프한 위치] = min(dp[점프한 위치], dp[현재위치] + 1);
dp[N-1] 출력

[ Source Code - BFS ]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, cnt = 0, result = 1000, visit[1001];
queue <int> q;

int main() {
    cin >> n;
    vector <int> maze(n+1);
    for(int i=1; i<=n; i++) {
        cin >> maze[i];
    }

    if(n == 1) {
        cout << "0";
        exit(0);
    }

    q.push(1);

    while(!q.empty()) {
        int pos = q.front();
        q.pop();
        if(maze[pos] == 0) continue;
        for(int i=1; i<=maze[pos]; i++) {
            if(visit[pos + i] == 0) {
                visit[pos + i] = visit[pos] + 1;
                q.push(pos + i);
            }
            if(pos + i >= n) {
                cout << visit[pos + i];
                exit(0);
            }
        }
    }

    cout << "-1";

    return 0;
}

💡 Idea - DP

1*N크기의 vector <int> jump(N); 생성
점프할 수 있는 크기를 jump[i]로 입력 받기
점프 횟수를 저장하기 위한 dp생성 후 처음 위치인 0은 점프 횟수가 0이므로 dp[0] = 0;
jump 배열 전체를 돌면서 점프할 수 있는 경우의 수 생각해보기
→ dp[점프한 위치]가 초기값이라면 dp[현재위치] + 1을 대입
→ 이미 값이 존재한다면 dp[현재위치] + 1 과 비교

dp[점프한 위치] = min(dp[점프한 위치], dp[현재위치] + 1);
dp[N] 출력

[ Source Code - DP ]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector <int> jump(N+1), dp(N+1, 2147000000);
    for(int i=1; i<=N; i++) {
        cin >> jump[i];
    }

    dp[1] = 0;

    for(int i=1; i<=N; i++) { // 현재 칸
        for(int j=0; j<=jump[i]; j++) { // 점프할 수 있는 칸 수
            if(i + j <= N) {
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }
    }

    if(dp[N] == 2147000000) {
        cout << "-1";
    }

    else cout << dp[N];

    return 0;
}