[BOJ 1697] 숨바꼭질 (java)

문제 링크 https://www.acmicpc.net/problem/1697

문제풀이

package basics_600;

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 BOJ1697 {
	static int count = 0;
	static boolean[] visited;
	static int MAX = 100000;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 수빈이 위치
		int N = Integer.parseInt(st.nextToken());
		// 동생 위치
		int K = Integer.parseInt(st.nextToken());
		// 방문 여부
		visited = new boolean[MAX+1];

		bfs(N,K);

	}

	static void bfs(int N, int K) {
		Queue<Integer> queue = new LinkedList<Integer>();
		// 루트 노드 방문
		visited[N] = true;
		// 큐에 넣기
		queue.offer(N);

		//큐 방문 
		while (!queue.isEmpty()) {
			//노드의 갯수만큼 
			int size = queue.size();
			
			for (int i = 0; i < size; i++) {
				//수빈이 위치 x
				int num = queue.peek();
				// x-1 이동 
				int back = queue.peek()-1;
				// x+1 이동 
				int front = queue.peek()+1;
				// x*2 이동 
				int jump = queue.peek()*2;
				
				queue.poll();
				
				//동생위치와 같다면 출력하고 루프 빠져나오기 
				if (num == K) {
					System.out.println(count);
					queue.clear();
					break;
				}
				
				//방문한적 없고 이동할 수 있는 위치라면 이동 
				if (back >= 0 && !visited[back]) {
					visited[back] = true;
					queue.offer(back);

				}
				if (front <= MAX && !visited[front]) {
					visited[front] = true;
					queue.offer(front);

				}
				if (jump <= MAX && !visited[jump]) {
					visited[jump] = true;
					queue.offer(jump);
				}
			}
			//depth 증가 
			count++;
		}

	}

}