[백준] 1697번 - 숨바꼭질

문제 >

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

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

 

입력 >

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

 

출력 >

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

 

해결방법 > 

BFS.

 

수빈이의 현재 위치에서 이동가능한 위치들을 너비우선탐색하면서

 

동생이 위치까지 최단시간으로 이동할 수 있는  경우를 찾는다.

 

1) N을 큐에 저장한다.

 

2) 큐에서 값을 하나 뽑아낸다.

 

3) 큐에서 뽑아낸 값 P와 인접한 위치(방문하지 않았으면서 P + 1, P - 1, P * 2인 위치)들을 방문하면서

 

K와 일치하는 지 확인하고 일치하지 않으면 다시 큐에 저장한다.

 

4) K와 일치하는 값을 찾을 때까지 2) - 3) 과정을 반복한다.

 

[JAVA]

package baekjoon;

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

public class BOJ_1697 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] a = br.readLine().split(" ");
		int n = Integer.parseInt(a[0]);
		int k = Integer.parseInt(a[1]);
		int[] visit = new int[100001];
		int sec = 0;
		Queue <Integer> q = new LinkedList<>();
		q.add(n);
		visit[n] = 1;
		
		while(!q.isEmpty()) {
			n = q.poll();
			if(n == k) {
				sec = visit[n] - 1;
				break;
			}
			if(n + 1 >= 0 && n + 1 <= 100000 && visit[n + 1] == 0) {
				visit[n + 1] = visit[n] + 1;
				q.add(n + 1);
			}
			if(n - 1 >= 0 && n - 1 <= 100000 && visit[n - 1] == 0) {
				visit[n - 1] = visit[n] + 1;
				q.add(n - 1);
			}
			if(n * 2 >= 0 && n * 2 <= 100000 && visit[n * 2] == 0) {
				visit[n * 2] = visit[n] + 1;
				q.add(n * 2);
			}
		}
		
		System.out.println(sec);
	}
}