숨바꼭질 (Silver I)

문제 링크

• 비슷한 문제 :

문제 설명

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

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

입력

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

출력

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

문제 풀이

• 문제 분류에 bfs 가 있기도 하고, bfs 공부하려고 찾다가 발견한 문제라서 bfs로 바로 풀었다
• 어떻게 bfs 로 풀지를 고민하는게 문제였는데
• 0초에서 부터 1초가 지날때마다 수빈이가 선택할 수 있는 방향은
  • x-1 / x+1 / x*2
• 해당 위치에 간 것을 확인해줄 int[] 배열을 만들어주어서 이전에 지나온 위치에서의 시간 +1초 해주었다
• 해당 위치에 값이 0이 아니라면 이미 방문했다는 것이고, 방문했다는 것은 지금 시간보다 더 빠른 시간내에 그 위치에 도착할 수 있다는 뜻이므로 갱신해주지 않는 것으로 한다.
• bfs 메서드 구현
  • 큐에 현재 위치를 넣고
  • 큐가 빌때까지 와일문 돌림
  • x = queue.poll();
  • x-1 / x+1 / x*2 값이 범위를 벗어나는지 확인
  • int[] 배열에서 x-1 / x+1 / x*2를 인덱스로 가지는 값이 0이 아닐때 또 큐에 넣어준다
  • 해당 x-1 / x+1 / x*2 배열의 값에는 +1 해준 시간을 넣어줌

Solution

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//숨바꼭질
public class Main {
	static int[] check = new int[100001];
	static int N;
	static int K;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();

		if (N == K) // 입력이 같을 때
			System.out.println(0);
		else {
			findK(N); // bfs
			System.out.println(check[K]); // 결과 출력
		}
	}

	public static void findK(int n) {
		Queue<Integer> que = new LinkedList<>(); // 큐 생성
		que.add(n);

		while (!que.isEmpty()) { // 큐가 빌때까지
			int X = que.poll(); // 현재 X

			if (X == K) // 값이 구해지면 스탑
				break;
			if (X > 0 && check[X - 1] == 0) { // X -1
				que.add(X - 1);
				check[X - 1] = check[X] + 1;
			}
			if (X + 1 < check.length && check[X + 1] == 0) { // X +1
				que.add(X + 1);
				check[X + 1] = check[X] + 1;
			}
			if (X * 2 < check.length && check[X * 2] == 0) { // X *2
				que.add(X * 2);
				check[X * 2] = check[X] + 1;
			}

		}
	}

}