[JAVA] 백준 - 13549 : 숨바꼭질3

문제 링크

13549번: 숨바꼭질 3

 

 

풀이 ) BFS

  방문한 요소에 대한 재방문을 방지하기 위해 boolean 배열을 선언해줬다.

  같은 depth에 있는 요소를 방문할 때 2배할때는 depth가 더 깊어지지 않기 때문에 queue의 앞에 삽입해주기 위해 deque를 사용했다.

  size만큼의 요소를 방문하면 depth가 늘어나기 때문에 앞에 삽입한 이후 size를 늘려준다.

 

  나중에 찾아보니 이런 방식으로 0-1BFS라고 한다고 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

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

        int n = Integer.parseInt(in[0]), k = Integer.parseInt(in[1]);
        boolean[] visited = new boolean[100001];
        if(k <= n){
            System.out.println(n-k);
            return;
        }

        Deque<Integer> deq = new ArrayDeque<>();
        deq.offer(n);
        int ans = -1;
        while(!deq.isEmpty()){
            ans++;
            int size = deq.size();
            while(size-- > 0){
                int cur = deq.poll();
                if(cur == k){
                    System.out.println(ans);
                    return;
                }
                visited[cur] = true;

                int tmp = cur*2;
                if(tmp <= 100000 && !visited[tmp]){
                    deq.offerFirst(tmp);
                    size++;
                }
                tmp = cur+1;
                if(tmp <= k && !visited[tmp])
                    deq.offerLast(tmp);

                tmp = cur-1;
                if(0 <= tmp && tmp <= 100000 && !visited[tmp])
                    deq.offerLast(tmp);
            }
        }
    }
}

 

주의 )

  처음에 위치를 x에서 x-1로 이동함에 있어서 k보다 큰 경우만 가능하도록 했지만 예제와 같이

  5 - 10 - 9 - 18 - 17에서 10 - 9와 같이 목표인 17보다 작아도 내려가는 경우가 있어서 다시 처리해줬다.