백준 12851 (숨바꼭질 2) - java

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

문제

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

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

 

유형 : BFS

 

주의 !

• 수빈이와 동생의 시작위치가 같은 경우 0 , 1 이 출력되어야 한다.
• 바로 찾는 것을 1로 생각한다고 한다.... (0초에 바로 찾았으니까)

 

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        if(n == m){
            System.out.println(0);
            System.out.println(1);
            return;
        }

        Queue<Integer> q = new LinkedList<>();
        q.add(n);

        int[] v = new int[100001];
        v[n] = 1;
        int result = 0;

        while(!q.isEmpty()){
            int cur = q.poll();

            for(int i=0;i<3;i++){
                int nx = cur;

                if(i == 0){
                    nx += 1;
                }

                if(i == 1){
                    nx -= 1;
                }

                if(i == 2){
                    nx = nx * 2;
                }

                if(nx < 0 || nx > 100000)
                    continue;

                if(nx == m){

                    if(v[m] == 0 || v[nx] > v[cur] + 1){
                        v[nx] = v[cur] + 1;
                        result = 1;
                    }

                    else if(v[nx] == v[cur] + 1){
                        result += 1;
                    }
                    continue;
                }

                if(v[nx] == 0 || v[nx] >= v[cur] + 1){
                    v[nx] = v[cur] + 1;
                    q.add(nx);
                }
            }
        }

        System.out.println(v[m] - 1);
        System.out.println(result);
    }
}