08. 송아지 찾기(BFS : 상태트리탐색)

 

설명

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요. 

 

 

 

 

입출력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.

 

 

 

예시

5 14 

 

3

 

 

 

 

풀이

1. 반드시 체크배열 써서 nx를 구하고 check[nx]=1처리 해주어야한다. 안하면 시간초과남

 

2. bfs를 쓰면 최소횟수를 구할수 있다.

import java.util.*;
class Main {

	int[] check = new int[10001];
	int[] moves= {1,-1,5};
	
	public int BFS(int s, int e) {
		int answer=0;
		
		Queue<Integer> queue= new LinkedList<>();
		check[s]=1;
		
		queue.add(s);
		int level=0;
		
		while(!queue.isEmpty()) {
			int size = queue.size();
			
			for(int i=0; i<size; i++) {
				int cur=queue.poll();
				for(int j=0; j<3; j++) {
					int nx=cur+moves[j];
					if(nx==e) {
						return level+1;
					}
					if(nx>=0 && nx<=10000 && check[nx]==0) {
						check[nx]=1;
						queue.offer(nx);
					}
				}
			}
			level++;
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int s=kb.nextInt();
		int e=kb.nextInt();
		System.out.println(T.BFS(s, e));
	}	
}