[백준 1697] 숨바꼭질

 

 

1차원 배열에서 BFS 순회한다.

수빈이는 뒤로도 이동할 수 있으므로 동생과 못 만날 경우는 없다.

이동 조건이 {-1, 1, 2*x} 인 것만 유의하자.

 

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int a[] = new int[100001];
        boolean visited[] = new boolean[100001];
        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.offer(n);
        visited[n] = true;
        a[n] = 0;
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            
            while(size-->0) {
                int me = queue.poll();
                int mx[] = {-1, 1, me};
                for(int i=0; i<3; i++) {
                    int nx = me + mx[i];
                    if(0 <= nx && nx < a.length) {
                        if(!visited[nx]) {
                            visited[nx] = true;
                            queue.offer(nx);
                            a[nx] = a[me] + 1;
                        }
                    }
                }
            }
        }
        System.out.println(a[k]);
    }
}