[백준저지] 1697번 : 숨바꼭질

www.acmicpc.net/problem/1697

1. 문제

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

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

입)

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

출)

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

2. 풀이

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        // 방문여부배열
        boolean[] check = new boolean[1000001];
        // 거리값
        int[] dist = new int[1000001];
        // 큐
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        check[n] = true;
        dist[n] = 0;
        // 큐에 값이 있을때까지 
        while (!queue.isEmpty()) {
            int x = queue.poll();
            // x-1
            if (x - 1 >= 0) {
                if (!check[x-1]) {
                    queue.add(x-1);
                    check[x-1] = true;
                    dist[x-1] = dist[x] + 1;
                }
            }
            // x+1
            if (x + 1 < 1000000) {
                if (!check[x+1]) {
                    queue.add(x+1);
                    check[x+1] = true;
                    dist[x+1] = dist[x] + 1;
                }
            }
            // 2*x
            if (2 * x < 1000000) {
                if (!check[2*x]) {
                    queue.add(2*x);
                    check[2*x] = true;
                    dist[2*x] = dist[x] + 1;
                }
            }
        }
        System.out.println(dist[k]);
    }
}

BFS를 이용해서 해결.