[백준] 13549번 숨바꼭질3

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

13549번: 숨바꼭질 3

 

* 2 의 경우 이동 시간이 0초라서 증가하지 않으므로 다른 이동 보다 먼저 계산되어야 함

 

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


class Node {
    int x;
    int time;

    public Node(int x, int time){
        this.x = x;
        this.time = time;
    }
}


public class Main {

    static int N, K;
    static boolean[] visit = new boolean[100001];
    static int time = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        if(N == K) {
        	System.out.println(0);
        } else {     
            bfs();
            System.out.println(time);
        }
    }

    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(N, 0));
        visit[N] = true;
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(node.x == K) {
            	time = Math.min(time, node.time);
            }
            int next;

            next = node.x * 2;
            if(next < 100001 && !visit[next]) {
                q.offer(new Node(next, node.time));
                visit[next] = true;
            }

            next = node.x -1;
            if(next >= 0 && !visit[next]) {
                q.offer(new Node(next, node.time + 1));
                visit[next] = true;
            }

            next = node.x + 1;
            if(next < 100001 && !visit[next]) {
                q.offer(new Node(next, node.time + 1));
                visit[next] = true;
        	}

        }
    }


}