백준 13549번 : 숨바꼭질 3 java

이 문에는 *2 +1 -1로 이동하면서 bfs에 노드들을 삽입하면서 문제를 해결하면 됩니다.

이때 유의하셔야 하는 점은 *로 가는 연산을 먼저 해야 연산 횟수를 줄일 수 있기 때문에 이 연산을 먼저 해야 한다는
것입니다.

또한 같은 자리에 나중에 도착하게 되더라도 *2할 때 걸리는 시간이 0이기 때문에 더 적은 시간으로 올 수도 있습니다.
따라서 min 변수를 Math.min으로 초기화하면서 저장해야 합니다.

이를 그림으로 설명드리겠습니다.

위의 그림과 같이 1 2 3 4이라는 수가 있습니다.

이를 +1연산으로만 채워보겠습니다.

그럼 각 자리까지 가는 시간은 위의 그림과 같습니다.

이제 *2연산을 더해보도록 하겠습니다.

1에서 시간한다고 할 때 2까지는 순간이동이니 시간이 들지 않고 4도 마찬가지입니다.

이때 더하기 연산을 한 후 Queue에 삽입하는 것을 먼저 두면 2에 2가 들어가게 되는데 *2 연산을 했을 때가 더 시간이 적게 걸립니다.

따라서 그 자리에서 최솟값을 비교하여 수를 대입하여야 합니다.

이제 코드를 보여드리겠습니다.

---

import java.util.*;
import java.io.*;

public class Main {
    static int K;
    //소요되는 시간을 줄이기 위해서 visited 선언
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new boolean[100_001];

        bfs(N);

        System.out.println(min);
    }

    static void bfs(int val){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(val, 0));
        visited[val] = true;

        while(!q.isEmpty()){
            Node a = q.poll();

            if(a.x == K)
                min = Math.min(min, a.time);

            if(a.x*2<=100_000 && !visited[a.x*2]){
                q.offer(new Node(a.x*2, a.time));
                visited[a.x*2] = true;
            }

            if(a.x-1>=0 && !visited[a.x-1]){
                q.offer(new Node(a.x-1, a.time + 1));
                visited[a.x-1] = true;
            }

            if(a.x+1<=100_000 && !visited[a.x+1]){
                q.offer(new Node(a.x+1, a.time + 1));
                visited[a.x+1] = true;
            }
        }
    }
}
class Node{
    int x, time;

    Node(int x, int time){
        this.x = x;
        this.time = time;
    }
}

위에서 설명드린 것과 같이 문제를 해결하였습니다.