[백준] 11060 점프 점프

11060번: 점프 점프

 

boj.kr

풀이

BFS와 동적계획법을 사용해서 해결했다. 현 위치에서 가장 멀리 뛴다고해서 최적해가 되지 않는다. 따라서 현 위치에서 뛸 수 있는 위치들을 모두 queue에 넣어줘서 최소값을 구했다.

코드

C++

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

int n;
vector<int> a, visited;

int bfs() {
    visited = vector<int>(n, 987654321);
    queue<int> q;
    q.push(0);
    visited[0] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int i = 1; i <= a[cur]; i++) {
            if (cur + i >= n) break; // 범위를 벗어나면 멈춘다
            if (visited[cur + i] > visited[cur] + 1) {
                visited[cur + i] = visited[cur] + 1;
                q.push(cur + i);
            }
        }
    }

    if (visited[n - 1] == 987654321) return -1;
    else return visited[n - 1];
}

int main() {
    cin >> n;
    a = vector<int>(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << bfs() << '\n';
    return 0;
}

Python3

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
a = list(map(int, sys.stdin.readline().rstrip().split()))
visited = [987654321] * n


def bfs():
    q = deque()
    q.append(0)
    visited[0] = 0

    while q:
        cur = q.popleft()

        for i in range(1, a[cur] + 1):
            if cur + i >= n: # 범위를 벗어나면 멈춘다
                break
            if visited[cur + i] > visited[cur] + 1:
                visited[cur + i] = visited[cur] + 1
                q.append(cur + i)
    if visited[n - 1] == 987654321:
        return -1
    else:
        return visited[n - 1]


print(bfs())