"숨바꼭질 3" - 13459번 G5

🐬 문제설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입출력 예

입력	출력
5 17	2
0 27	3

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 0-1 너비 우선 탐색

강의내용

✔️현재 시간과 다음 시간을 체크하는 큐를 2개 생성하고 번갈아가면서 시간을 체크한다.
✔️큐2개를 이용하는 대신 덱을 이용하면 1개만으로 풀이가 가능하다.

🌟문제 이해 및 풀이계획

✏️큐 2개를 이용하여 queue는 순간이동(*2, 0초), next_queue는 걸을 때(-1, +1, 1초)를 담는다.
✏️queue에 모든 순간이동 지점을 담고, 목적지점 k인지 체크한다.
✏️k점이면 return하고, 아니면 next_queue에 걷고난 후의 지점을 담는다.(-1, +1)
✏️최단 시간을 검사해야 하기 때문에 큐에서 poll할 때 방문처리 한다.

✍🏻내 코드1 - 정답코드

package BOJ;

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

/*
 * 2022.07.04 daily algorithm
 * 
 * BFS - 최단시간 구하기
 * 큐 2개를 사용하여 현재시간 큐, 다음시간 큐로 설정하여 현재시간 큐가 비면 
 * 현재시간 큐 = 다음시간 큐 로 변환하여 다시 다음시간 큐로 진행한다.
 * 
 * 최단 시간을 구해야하기 때문에 큐에서 나올 때 방문처리를 해준다. 
 */

public class boj_13549 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		sc.close();
		
		bfs(n, k);
		System.out.println(time);
	}

	static boolean[] visited = new boolean[100001];
	static int time = 0;
	public static void bfs(int n, int k) {
		Queue<Integer> queue = new LinkedList<>();
		Queue<Integer> next_queue = new LinkedList<>();
		queue.add(n);
		
		while(!queue.isEmpty()) {
			int p = queue.poll();
			visited[p] = true;
			if(p == k) break;
			
			if(p*2 <= 100000 && !visited[p*2]) {
				queue.add(p*2);
			}
			if(p-1 >= 0 && !visited[p-1]) next_queue.add(p-1);
			if(p+1 <= 100000 && !visited[p+1]) next_queue.add(p+1);
			
			if(queue.isEmpty()) {
				queue = next_queue;
				next_queue = new LinkedList<Integer>();
				time += 1;
			}
		}
	}
	
}