[BOJ/백준 - 1697] 숨바꼭질

문제 출처: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

	public class BOJ_TEMP {
	public static void main(String[] args) throws Exception{
	// INPUT & INIT
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	if(a > b) {
	System.out.println(a - b);
	return;
	}else if (a == b) {
	System.out.println(0);
	return;
	}
	int[] arr = new int[100001];
	int target = a;
	Queue<Integer> q = new LinkedList<>();
	q.add(target);
	while(!q.isEmpty()) {
	int cur = q.poll();
	for(int i=0; i<3; i++) {
	int next = 0;
	if(i==0) {
	next = cur-1;
	}else if(i==1) {
	next = cur+1;
	}else {
	next = cur*2;
	}
	if(0 <= next && next <= 100000 && arr[next] == 0) {
	arr[next] = arr[cur]+1;
	q.add(next);
	}
	}
	}
	System.out.println(arr[b]);
	}
	}

view raw BOJ_1697.java hosted with ❤ by GitHub

---

기본적인 형태의 BFS풀이로 진행