[BFS] BOJ 1697번, 숨바꼭질 (JAVA)

숨바꼭질

문제

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

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

입력

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

출력

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

---

문제풀이

 

수빈이의 위치 N 에서  -----------> 동생의 위치 K 로 가는 최소 시간을 구하는 문제.

 

처음 배열의 초기화를 int[] dist = new int[n or k] 이런식으로 해서 index 문제가 발생하였다.

 

문제를 읽어보면 배열이 앞으로 한칸, 뒤로 한칸, X2 위치 이동 이 가능하므로 배열 초기화를 최대범위로 해주어야 했다.

 

---

소스코드

import java.util.*;
import java.io.*;
class Main{
	static int n, k;
	static int[] dist = new int[100001];
	static int ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		bfs(n);
		System.out.println(dist[k]);
	}
	
	public static void bfs(int start)
	{
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		
		while(!q.isEmpty())
		{
			int now = q.poll();
			if(now == k)
			{
				break;
			}
			int moves[] = {now-1, now+1, now*2};
			for(int i=0;i<3;i++)
			{
				int next = moves[i];
				if(next>=0 && next<=100000 && dist[next] == 0)
				{
					q.add(next);
					dist[next] = dist[now] + 1;
				}
			}
		}
	}
}