[백준/자바] 1697 숨바꼭질

1697 숨바꼭질 사진 클릭시 문제로 이동

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다.

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

입력

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

N과 K는 정수이다.

출력

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

예제 입력 1

5 17

예제 출력 1

4

---

설명

해당 문제는 다음과 같은 알고리즘 분류에 해당하는 문제다.

• 그래프 이론

• 그래프 탐색

• 너비 우선 탐색 

수빈이의 위치가 X일 때 X-1, X+1, 2*X의 위치로 이동할 수 있다.

방문 여부를 표시하는 visited와 해당 위치까지 이르는 시간을 표시하는 num변수를 설정한다.

이때, 수빈과 동생 모두 100000까지 거리를 이동할 수 있으므로 배열의 범위는 100001까지 지정한다.

위치 이동시 무조건 1초씩 이동하기 때문에 num++한다.

코드

	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	public class BOJ1697 {
	static int min;
	static boolean visited[];
	static int num[];
	static int X[] = {-1,1,2};
	static Queue<Integer> q = new LinkedList<>();
	public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int m = scanner.nextInt();
	visited = new boolean[100001];
	num = new int[100001];
	bfs(n,m);
	}
	private static void bfs(int start, int end) {
	q.add(start);
	while(!q.isEmpty()) {
	int cur = q.poll();
	if(cur == end) {
	System.out.println(num[end]);
	return;
	}
	for(int i = 0; i < 3; i++) {
	int x = 0;
	if(i == 2) {
	x = cur * X[i];
	}else {
	x = cur + X[i];
	}
	// 범위 초과
	if(x < 0 || 100000 < x) {
	continue;
	}
	if(!visited[x]) {
	q.add(x);
	num[x] = num[cur] + 1;
	visited[x] = true;
	if(x == end) {
	System.out.println(num[end]);
	return;
	}
	}
	}
	}
	}
	}

view raw BOJ1697.java hosted with ❤ by GitHub