백준 1697. 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제제목 : 숨바꼭질

문제유형 : BFS

문제난이도 : 실버1

 

문제

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

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

입력

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

출력

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

 

아이디어

- 특정 위치까지 이동하는 최단 시간을 계산하는 문제이다.

- 이동시간이 모두 1초이므로 너비우선탐백을 이용하여 해결.

- 큐를 구현함. (BFS이므로)

 

@ 5에서 7로 가는 최단거리

코드

package week4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

/*
 * 숨바꼭질 https://www.acmicpc.net/problem/1697
 * 문제유형 : BFS
 * 
 */

public class BOJ1697 {
	private static int MAX = 100001;
	private static int n, k;
	private static int[] data = new int[MAX]; // 최대 100,000

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		
		n = Integer.valueOf(input[0]);
		k = Integer.valueOf(input[1]);
		
		BFS(n);
		
		bw.write(String.valueOf(data[k]));
		bw.flush();
		bw.close();
	}
	
	public static void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		
		while (!queue.isEmpty()) { // 큐가 비어있으면 종료
			int num = queue.poll();
			
			if (num == k) { // 술래잡기 성공 시 카운트 출력
				return;
			}
			
			int next = num - 1;
			if (0 <= next && next < MAX && data[next] == 0) {
				data[next] = data[num] + 1;
				queue.add(next);
			}
			next = num + 1;
			if (0 <= next && next < MAX && data[next] == 0) {
				data[next] = data[num] + 1;
				queue.add(next);
			}
			
			next = num * 2;
			if (0 <= next && next < MAX && data[next] == 0) {
				data[next] = data[num] + 1;
				queue.add(next);
			}
		}
	}

}