백준 11060번: 점프 점프

문제 설명

• https://www.acmicpc.net/problem/11060
• 왼쪽 끝에서 오른쪽 끝으로 이동합니다. 해당 칸에 적혀있는 숫자 이하로 점프할 수 있습니다. 이때 최소 이동 횟수를 구하는 문제입니다.

접근법

• 숫자가 arr[i]인 i번째 칸에 도착했다면 i+1부터 i+arr[i]번째 사이의 칸을 다음 이동할 칸으로 선택할 수 있습니다.

정답

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		System.out.println(BFS(arr));
	}
	
	public static int BFS(int[] arr) {
		int start = 0;
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] v = new boolean[arr.length];
		q.add(start);
		int cnt = 0;
		while(!q.isEmpty()) {
			int size = q.size();			
			while(--size>=0) {
				int now = q.poll();
				if(now == arr.length-1) {
					return cnt;
				}
				for (int i = now+1; i < Math.min(arr.length, now+1+arr[now]); i++) {
					if(v[i]) continue;
					v[i] = true;
					q.add(i);
				}
			}
			cnt++;
		}
		return -1;
	}

}