[BOJ] 1697 숨바꼭질

[문제]

https://www.acmicpc.net/problem/1697

 

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Solution {
	public static void main(String[] args) throws IOException {
		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());
		int[] diff = new int[200001];
		Arrays.fill(diff, -1);
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[]{n,0});
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			if(curr[0]==k) {
				System.out.println(curr[1]);
				return;
			}
			if(curr[0]-1>=0 && diff[curr[0]-1]==-1) {
				q.offer(new int[] {curr[0]-1,curr[1]+1});
				diff[curr[0]-1] = curr[1] + 1;
			}
			if(curr[0]+1<=200000 && diff[curr[0]+1]==-1) {
				q.offer(new int[] {curr[0]+1,curr[1]+1});
				diff[curr[0]+1] = curr[1] + 1;
			}
			if(curr[0]*2<=200000 && diff[curr[0]*2]==-1) {
				q.offer(new int[] {curr[0]*2,curr[1]+1});
				diff[curr[0]*2] = curr[1] + 1;
			}
		}
	}
}