[BOJ] 11060: 점프 점프 (JAVA)

11060번: 점프 점프

 

헤맸던 부분 (반례)

 

1x1 미로에 갇혔을 경우, 점프를 하지 않고 도착하기 때문에 0이 출력되어야 한다.

 

이 부분을 고려하니 해결된 문제. 숨바꼭질과 비슷했다.

 

package 백준renew;

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

public class 실버2_11060_점프점프 {
	static int N, cnt;
	static int map[];
	static int visited[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		map = new int[N];
		visited = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		BFS();
		
		if(visited[map.length-1] == 0) {
			if(N == 1) {
				sb.append(visited[map.length-1]);
			}else {
				sb.append("-1");
			}
		}else {
			sb.append(visited[map.length-1]);
		}
		
		System.out.println(sb.toString());
		
	}
	static void BFS() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		
		while(!queue.isEmpty()){
			int now = queue.poll();
			
			int go = map[now];
			
			for(int i=0; i<go; i++) {
				int newX = now + (i+1);
				
				if(newX >= N || visited[newX] != 0) {
					continue;
				}
				
				queue.add(newX);
				visited[newX] = visited[now] + 1;
			}
		}
	}
}