[백준] [BFS] 1697. 숨바꼭질

• 한 곳 방문하면 다음에 x-1, x+1, 2*n  3곳을 방문하게 된다
  • ->  1:N : bfs
  • queue에 현재 위치(depth =n) 에 연결된 곳들(depth=n+1) 을 넣어준다 
• visited값에 시간 바로 추가
• 앞에서 먼저 그 위치에 방문한 시간이 어짜피 최소값
  • -> 앞에서 방문한 곳은 갈 필요x

package day14_bfs;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class JUN1697_ParkSomin {
    static int n,k;
    static int[] visited;
    static Queue<Integer> q;
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();

        q=new ArrayDeque<>();
        visited=new int[100001]; //visited값에 시간 바로 추가
        visited[n]=1; //0인 상태는 방문 전으로 인식하기 때문에 1초부터 시작해서 결과 -1해준다

        //x-1, x+1, 2*n : 1:N
        bfs(n); //첫 위치: n


    }

    //d: 수빈이 위치
    //앞에서 먼저 그 위치에 방문한 시간이 어짜피 최소값
    //앞에서 방문한 곳은 갈 필요x
    private static void bfs(int d){
        q.offer(d);
        while (!q.isEmpty()){
            int x=q.poll();
            if(x==k){
                System.out.println(visited[x]-1);
            }

            int next=x+1;
            if (next<100001 && visited[next]==0){ //이미 방문한 경우 가지x
                visited[next]= visited[x]+1;
                q.offer(next);
            }


            next=x-1;
            if (next>=0 && visited[next]==0){
                visited[next]= visited[x]+1;
                q.offer(next);
            }


            next=2*x;
            if (next<100001 && visited[next]==0){
                visited[next]= visited[x]+1;
                q.offer(next);
            }
        }
    }

}