백준 12851번 숨바꼭질 2 (JAVA)

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

12851번: 숨바꼭질 2

 

처음에는 방문체크를 하지 않고 진행하여 메모리 초과가 나왔습니다. 

visited배열을 통해 방문 체크를 하였습니다. 하지만 해당하는 경우의 수도 같이 출력해야하기 때문에 Queue에 넣을 때 visited를 true로 만들지 않고 queue에서 깨낼 때 visited를 true로 만들었습니다.

그리고 배열의 크기는 LIMIT의 2배까지 되게 만든 이유는 2배로 갔다가 뒤로 가는 경우도 존재할 수 있다고 생각하였습니다. 근데 2 * LIMIT 이상이라면 더 효율적이게 될 것이라 판단하여 이 이상가는 것은 막았습니다. 

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_12851 {
    static int n,m;
    static final int LIMIT = 100_000;
    static boolean visited[] = new boolean[2*LIMIT+1];
    static void cal(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(n);
        int time = 0;
        int cnt =0;
        boolean flag = false;
        while(!q.isEmpty()){
            int size = q.size();
            for(int t = 0 ; t < size ; t++){
                int now = q.poll();
                visited[now] = true;
                if(now == m){
                    flag = true;
                    cnt++;
                }
                if(now -1 >=0 && !visited[now-1]){
                    q.offer(now - 1);
                }
                if(now + 1 <= LIMIT && !visited[now+1]){
                    q.offer(now + 1);
                }
                if(now < LIMIT && !visited[2 * now]){
                    q.offer(2 * now);
                }
            }
            if(flag){
                break;
            }
            time++;
        }
        System.out.println(time);
        System.out.println(cnt);
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        n = stoi.apply(st.nextToken());
        m = stoi.apply(st.nextToken());
        cal();
    }
}