[알고리즘] 송아지 찾기 (BFS)

 

 

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

 

https://cote.inflearn.com/contest/10/problem/07-08

OnlineJudge

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
  
public class Main {
	
	static int[] dis = {-1, 1, 5};
	
	public static void main(String[] args){
	  
	  Scanner sc =new Scanner(System.in);
	  
	  int input1 = sc.nextInt();
	  int input2 = sc.nextInt();
    
	  BFS(input1, input2);
	  
  }
  
  static void BFS(int input1, int input2) {
	  
	  boolean[] check = new boolean[10001];
	  
	  int level = 0;
	  
	  Queue<Integer> queue = new LinkedList<>();
	  
	  queue.offer(input1);
	  
	  check[input1] = true;
	  
	  while(!queue.isEmpty()) {
		  int size = queue.size();
		  
		  for(int i=0; i<size; i++) {
			  int x = queue.poll();
			  
			  for(int k=0; k<3; k++) {
				  int newX = x + dis[k];
				  if(newX == input2) {
					  System.out.println(level+1);
					  return;
				  }
				  
				  if(1 <=newX && newX<=10000 && check[newX]==false) {
					  check[newX] = true;
					  queue.offer(newX);
				  }
				  
			  }
			  
		  }
		  level++;
		  
	  } // end of while

	  
  }
}