[Java] 백준 11060번 : 점프 점프

문제

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

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

입력

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

출력

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

예제 입력 1

10
1 2 0 1 3 2 1 5 4 2

예제 출력 1

5

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, jump = 1;
	private static int[] maze;

	static class Jump {
		int idx, cnt;

		public Jump(int idx, int cnt) {
			super();
			this.idx = idx;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Jump [idx=" + idx + ", cnt=" + cnt + "]";
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		maze = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			maze[i] = Integer.parseInt(st.nextToken());
		System.out.println(bfs());
	}

	private static int bfs() {	// bfs를 통해 가장 먼저 오른쪽 끝에 도달하는 경우의 수를 구해줌
		Queue<Jump> queue=new LinkedList<>();
		queue.add(new Jump(0, 0));
		
		boolean []visited=new boolean[N];
		visited[0]=true;
		
		while(!queue.isEmpty()) {
			Jump q=queue.poll();
			
            if(q.idx>=N-1) return q.cnt; 
			for(int i=1;i<=maze[q.idx];i++) {
				if(q.idx+i>=N-1) return q.cnt+1;
				if(!visited[q.idx+i]) {
					visited[q.idx+i]=true;
					queue.add(new Jump(q.idx+i, q.cnt+1));
				}
			}
		}
		return -1;
	}
}

최소 횟수를 구해야하므로 bfs를 이용하여 가장 먼저 오른쪽 끝에 도달하는 경우를 구해주었습니다.