백준 1697번 : 숨바꼭질 자바

https://www.acmicpc.net/problem/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, +1, *2 이세가지 행동을 할 수 있기 때문에 현재위치를 큐에서 꺼낸후 세가지 연산을 진행한후 count+1 해주면 그 위치를 갈 수 있는 가장 빠른 시간이 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    int N = Integer.valueOf(stringTokenizer.nextToken());
    int K = Integer.valueOf(stringTokenizer.nextToken());
    int[] dp = new int[100001];
    Arrays.fill(dp,Integer.MAX_VALUE);
    dp[N] = 0;

    Queue<Integer> queue = new LinkedList();
    queue.add(N);

    while (!queue.isEmpty()){
      int n = queue.poll();
      int plus = n+1;
      int minus = n-1;
      int multiple = n*2;

      if (multiple<100001&&dp[multiple]==Integer.MAX_VALUE){
        dp[multiple] = dp[n]+1;
        queue.add(multiple);
      }
      if (plus<100001&&dp[plus]==Integer.MAX_VALUE){
        dp[plus] = dp[n]+1;
        queue.add(plus);
      }
      if (minus>=0&&dp[minus]==Integer.MAX_VALUE){
        dp[minus] = dp[n]+1;
        queue.add(minus);
      }

      if (dp[K]!=Integer.MAX_VALUE){
        System.out.println(dp[K]);
        return;
      }
    }

  }
}