[백준 1697 숨바꼭질 - 자바(JAVA)]

문제 풀이 시나리오

1.BFS
2.수빈이의 위치가 x 일때 x-1 / x+1 /2*x 위치로 이동가능
3.큐에 시작 노드 추가하고
4.1차원 board에 이동에 걸린 시간 저장

5.목적지를 뽑으면 그 값을 리턴

6.이미 걸린 시간을 저장한 노드이면 넘기고
7.이동가능한 인덱스이고 이미 저장하지 않았다면 큐에 저장

풀이

package baekjoon;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;



public class Main {
	static int[] board = new int[100001];//0 ~ 10,0000
	static Queue<Integer> q = new LinkedList<Integer>();
	static int Move(int idx ,int cur) {
		switch(idx){
			case 0:
				return cur +1;
			case 1:
				return cur -1;
			case 2:
				return cur*2;
			
		}
		return 0;
	}
	

	static boolean[] visited = new boolean[100001];
	public static int BFS() {
		int cur = 0;
		while(!q.isEmpty() ) {
			cur = q.poll();
			visited[cur] = true;
			if(cur == end)
				break;
			
			//세번 이동
			for (int i = 0; i< 3 ;i++) {
				//순간이동한 노드
			
				int next = Move(i,cur);
				
				if(next <0 || next > 100000)
					continue;
				//이미 방문한 좌표
 				if(board[next] != 0)
					continue;
				//걸린 시간 저장
				board[next] = board[cur] + 1;
				//큐에 저장
				q.offer(next);
				
			}
			
		}
		return board[cur] - 1;
	}
	static int start;
	static int end;
	
    public static void main(String[] args) throws IOException {
    	Scanner scan = new Scanner(System.in);
        start = scan.nextInt();
    	end = scan.nextInt();
    	q.offer(start);
    	board[start] = 1;
    	System.out.println(BFS());
    	
    }
}