[Java] 백준 1326번 : 폴짝폴짝

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1

5
1 2 2 1 2
1 5

예제 출력 1

1

힌트

1번 징검다리에 1이 쓰여 있으므로, 1의 배수인 4만큼을 한 번에 뛰어 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, A, B;
	private static int []bridge;
	
	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());
		bridge=new int[N+1];
		
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) bridge[i]=Integer.parseInt(st.nextToken());
		st=new StringTokenizer(br.readLine());
		A=Integer.parseInt(st.nextToken());
		B=Integer.parseInt(st.nextToken());
		
		System.out.println(bfs());
	}

	private static int bfs() {
		Queue<Jump> queue=new LinkedList<>();
		queue.add(new Jump(A, 0));
		
		boolean []visited=new boolean[N+1];
		visited[A]=true;
		
		while(!queue.isEmpty()) {
			Jump j=queue.poll();
			
			if(j.idx==B) {
				return j.cnt;
			}
			int now=1;
			while(true) {	// 오른쪽
				int val=now*bridge[j.idx];
				if(val+j.idx>N) break;
				if(!visited[val+j.idx]) {
					visited[val+j.idx]=true;
					queue.add(new Jump(val+j.idx, j.cnt+1));
				}
				now++;
			}
			
			now=1;
			while(true) {	// 왼쪽
				int val=now*bridge[j.idx];
				if(j.idx-val<=0) break;
				if(!visited[j.idx-val]) {
					visited[j.idx-val]=true;
					queue.add(new Jump(j.idx-val, j.cnt+1));
				}
				now++;
			}
		}
		return -1;
	}
}

최소 횟수를 구해야하므로 bfs를 이용하였습니다. 이때 현재 위치의 배수만큼 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우를 나누어 결과를 구해주었습니다.