백준 1697 - 숨바꼭질 (JAVA 자바 풀이)

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

1697번: 숨바꼭질

 

BFS로 풀었습니다. 

한번 큐에 담았던 숫자는 다시 큐에 담지 않도록 방문처리는 반드시 해주셔야 됩니다. 

아래 반례들을 참고해서 풀어보세요.

 

<반례1>

입력 : 100000 0

출력 : 100000

 

<반례2>

입력 : 0 100000

출력 : 22

 

<반례3>

입력 : 0 0

출력 : 0

 

 

 

 

import java.io.*;
import java.util.*;
 
public class test {
 
    static int N,K;
    static boolean visits[];
 
    public static void main(String args[]) throws Exception {
 
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt(); // 5
        K = sc.nextInt(); // 17
        visits = new boolean[100001];
 
        if (N == K) {
            System.out.println("0");
            return;
        }
        if (K < N) {
            System.out.println(N - K);
            return;
        }
 
        Queue<List> q = new LinkedList();
 
        q.add(Arrays.asList(N,0)); // 5, 0 (현재위치, 소요시간)
 
        int ans = Integer.MAX_VALUE;
 
        while(!q.isEmpty()){
            List out = q.poll(); // 5 , 0
 
            int cur = (int) out.get(0); // 5
            int time = (int) out.get(1); // 0
 
            if (visits[cur]) continue;
            visits[cur] = true;
 
            // 2를 곱했을 때, 1을 더했을 때, 1을 뺐을 때를 각각 q에 넣어준다
 
            List nextP = Arrays.asList(cur+1, time+1);
            List nextN = Arrays.asList(cur-1, time+1);
            List next2X = Arrays.asList(cur*2, time+1);
 
//            System.out.println("cur : " + cur + " | time : " + time + " | 다음+1 이동위치 : " + nextP.get(0) + " | 다음-1 이동위치 : " + nextN.get(0) + " | 2배 순간이동 위치 : " + next2X.get(0));
 
            if ((int)nextP.get(0) == K) {
                ans = Math.min(ans, (int)nextP.get(1));
                break;
            }
            if ((int)nextN.get(0) == K) {
                ans = Math.min(ans, (int)nextN.get(1));
                break;
            }
            if ((int)next2X.get(0) == K) {
                ans = Math.min(ans, (int)next2X.get(1));
                break;
            }
 
            if ((int)nextP.get(0)<=100000 && !visits[(int)nextP.get(0)]) q.add(nextP);
            if ((int)nextN.get(0)>=0 && !visits[(int)nextN.get(0)]) q.add(nextN);
            if ((int)next2X.get(0)<=100000 && !visits[(int)next2X.get(0)]) q.add(next2X);
        }
 
        System.out.println(ans);
 
    }
 
}