개구리 뛰기 - BFS

SCPC 2015 1차 예선

문제

일직선 상에 돌들이 놓여있고, 개구리가 처음에는 '좌표 0'에 위치한 돌 위에 앉아 있다.
'좌표 0'에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1)

개구리는 점프를 통해서 돌들 사이를 이동해서 마지막 돌까지 이동해야 한다.
이 때, 개구리가 한번의 점프로 이동 가능한 최대 거리 K 가 주어진다.
개구리는 한번의 점프로 자신이 앉아 있던 돌에서  K 이하의 거리에 위치한 돌들 중 하나의 돌로 이동 할 수 있다. 
여기서 문제는, '좌표 0'에 위치한 개구리가 마지막 돌까지 이동할 수 있다면,
마지막 돌까지 이동하기 위한 최소 점프 횟수를 계산하는 것이다. 

예를 들어서, 위의 "그림1"의 예에서 보면, 한번의 점프로 이동 가능한 최대 거리가 K=4 로 주어질 때,
아래 "그림2"에서와 같이 5회의 점프로 마지막 돌로 이동할 수 있고, 이것이 최소의 점프 횟수이다. 

또한 위의 예에서, K=2 로 주어진다면 개구리는 마지막 돌로 이동할 수가 없다.
왜냐하면, 개구리가 '좌표 2'의 돌로 이동한 후 '좌표 5'이상의 돌로는 이동할 수 없기 때문이다. 



- 제한시간 : 전체 테스트 케이스는 5개 이하이며, 전체 수행 시간은 1초 이내 (Java 2초 이내) 
    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
    그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.

- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
- 제출 제한 : 최대 7회

입력

입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T가 주어지고,
이후 차례로 T개의 테스트 케이스가 주어진다. ( 1≤T≤5 ) 
각각의 테스트 케이스 첫 번째 줄에는 '좌표 0'에 놓인 돌을 제외한 나머지 돌들의 개수 N 이 주어진다. ( 1≤N≤1,000,000 )
두 번째 줄에는 돌들이 놓인 좌표를 나타내는 N 개의 정수 ai들이 빈칸(공백)을 사이에 두고 주어진다. (1≤ai≤10⁹ )
여기서, 주어진 좌표들은 증가하는 순서로 주어지고 모두 다르다.
세 번째 줄에는 개구리가 한 번의 점프로 이동 가능한 최대 거리 K 가 주어진다. ( 1≤K≤10⁹ )

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다.
이때 T는 테스트 케이스의 번호이다.
그 다음 줄에는 개구리가 마지막 돌로 이동할 수 있는 최소 점프 횟수를 출력한다.
만약, 개구리가 마지막 돌로 이동하는 것이 불가능한 경우에는 "-1"을 출력한다.

입출력예

입력

3
8
1 2 5 7 9 10 12 15
4
8
1 2 5 7 9 10 12 15
2
17
3 4 8 10 14 18 20 22 23 25 30 33 34 36 38 39 42
7

출력

Case #1
5
Case #2
-1
Case #3
8

풀이 방법

문제를 보자마자 시작점에서 목표까지의 최단 경로를 찾는 BFS 알고리즘이 떠올랐다.
다음은 BFS 알고리즘을 사용해서 최소 점프 횟수 ( 최소 방문 횟수 ) 를 구하는 코드이다.
세부 설명은 주석으로 달아놔야지

/*
You should use the statndard input/output

in order to receive a score properly.

Do not use file input and output

Please be very careful. 
*/

import java.util.Scanner;
import java.util.*;

/*
   As the name of the class should be Solution , using Solution.java as the filename is recommended.
   In any case, you can execute your program by running 'java Solution' command.
 */
class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		/*
		   The method below means that the program will read from input.txt, instead of standard(keyboard) input.
		   To test your program, you may save input data in input.txt file,
		   and call below method to read from the file when using nextInt() method.
		   You may remove the comment symbols(//) in the below statement and use it.
		   But before submission, you must remove the freopen function or rewrite comment symbols(//).
		 */		

		/*
		   Make new scanner from standard input System.in, and read data.
		 */
		Scanner sc = new Scanner(System.in);
		//Scanner sc = new Scanner(new FileInputStream("input.txt"));

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {

			// Answer = 0;
			/////////////////////////////////////////////////////////////////////////////////////////////
			int N = sc.nextInt();
			int[] stones = new int[N+1];
			stones[0] = 0;
			for (int i = 1; i <= N; i++) {
			    stones[i] = sc.nextInt();
			}
			int K = sc.nextInt();
			
			Answer = minJumps(stones, K);
			/////////////////////////////////////////////////////////////////////////////////////////////


			// Print the answer to standard output(screen).
			System.out.println("Case #"+(test_case+1));
			System.out.println(Answer);
		}
	}
	
	public static int minJumps(int[] stones, int K ) {
	    int n = stones.length;
		
        // BFS 큐 초기화 (현재 위치, 현재 점프 횟수)
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); 

		// 중복 방지
        boolean[] visited = new boolean[n];
        visited[0] = true; // 시작점 중복 방지 처리

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int position = current[0];
            int jumps = current[1];

			// 현재 위치에서 K 이하로 이동 가능한 모든 위치를 탐색
            for (int i = position + 1; i < n && stones[i] - stones[position] <= K; i++) {
                if (!visited[i]) {
                	// 마지막 돌에 도달한 경우 점프 횟수 반환
                    if (i == n - 1) {
                        return jumps + 1;
                    }
                    // 다음 위치르 ㄹ큐에 추가하고 중복 방지 처리
                    queue.offer(new int[]{i, jumps + 1});
                    visited[i] = true;
                }
            }
        }
        // 마지막 돌에 도달할 수 없는 경우 -1 반환
        return -1;
	}
}