백준 1697번

숨바꼭질

문제

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

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

입력

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

출력

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

예제

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

코드

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

public class Main {	
	static int check[] = new int[100001];
	
	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());
		
		if(N == K)
			System.out.println(0);
		else
			BFS(N, K);
	}
	
	public static void BFS(int N, int K) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(N);
		check[N] = 1;
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			for(int i=0; i<3; i++) {
				int next;
				
				if(i == 0)
					next = temp + 1;
				else if(i == 1)
					next = temp - 1;
				else
					next = temp * 2;
				
				if(next == K) {
					System.out.println(check[temp]);
					return;
				}
				
				if(next < 0 || next >= 	check.length || check[next] != 0)
					continue;
				
				queue.add(next);
				check[next] = check[temp] + 1;
			}
		}
	}
}

풀이

매 순간에서 가능한 경우의수를 다 따지는 방식이므로, 너비 우선 탐색 BFS가 적절하다.

count int 변수로 초를 세는것 보다 check[] 처럼 1차원 배열을 활용하는 것이 더 편하다.