[JAVA]백준 - 1697번 숨바꼭질 (실버1)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int arr[] = new int[100001];
		Queue<Integer> q = new LinkedList<>();
		
		q.offer(N);
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			if(cur == K) {
				System.out.println(arr[cur]);
				break;
			}
			
			
			if(cur-1 >= 0 && arr[cur-1]==0) {
				arr[cur-1] = arr[cur]+1;
				q.offer(cur-1);
			}
			if(cur+1 < arr.length && arr[cur+1]==0) {
				arr[cur+1] = arr[cur]+1;
				q.offer(cur+1);
			}
			if(cur*2 < arr.length && arr[cur*2]==0) {
				arr[cur*2] = arr[cur]+1;
				q.offer(cur*2);
			}
		}
		
	}
}

• 큐를 사용하여 BFS 탐색을 수행
• N을 큐에 추가하고 탐색 시작
• 큐에서 cur(현재 위치) 하나씩 꺼내면서, 도착하면(cur == K) 즉시 이동 횟수 출력 후 종료
• 이동할 수 있는 위치 cur-1, cur+1, cur*2 중 방문하지 않은 곳을 탐색
• arr[next] = arr[cur] + 1로 이동 횟수 업데이트 후 큐에 추가
• 최단 시간 출력(arr[K])