1697-숨바꼭질

 

1697번: 숨바꼭질

 

저번에 풀었던 스타트링크와 엄청 유사한 문제다

각각 N+1 N-1 N*2 이 조건문을 만족하면 큐에 넣어준다

그리고 bfs 상단의 if문으로 최단 거리를 구해준다

 

Node를 사용하지않고 while문을 통과할때마다 count++ 해주어 

sout(count)를 해도 좋을 것 같다

 

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

public class B1697 {
    static int N,K;
    static int res= 0;
    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        bfs();
        System.out.println(res);
    }
    static class Node{
        int p,m;
        Node(int position, int move){
            p = position;
            m = move;
        }
    }

    private static void bfs() {
       Queue<Node> queue = new LinkedList<>();
       visited[N] = true;
       queue.add(new Node(N,0));
       while(!queue.isEmpty()){
           Node temp = queue.remove();
           if(temp.p==K) {
               if(res==0) res= temp.m;
               if(res>temp.p) res = temp.m;
               break;
           }
           if((temp.p+1)<100001 && !visited[temp.p+1]){
               visited[temp.p+1] = true;
               queue.add(new Node((temp.p+1), temp.m+1));
           }
           if((temp.p-1)>=0&&!visited[temp.p-1]){
               visited[temp.p-1] = true;
               queue.add(new Node((temp.p-1), temp.m+1));
           }
           if((temp.p*2)<100001 && !visited[temp.p*2]){
               visited[temp.p*2] = true;
               queue.add(new Node((temp.p*2), temp.m+1));
           }
       }
    }
}