[BOJ] 13549. 숨바꼭질3 - 자바 JAVA

13549번: 숨바꼭질 3

• BFS

최소비용을 찾는 문제로 BFS로 해결할 수 있었다.

 

수빈이의 위치와 시간을 저장하는 Node 클래스를 생성한 후, 3가지 연산(*2, +1, -1)을 수행하며 K까지 도달했을 때 최소 시간을 저장해준다. N, K의 범위는 0 ~ 100,000 으로 *2와 +1 연산을 할 때, 100,000을 초과되지 않도록 주의하고, -1 연산을 할 때, 0 미만이 되지 않도록 주의해준다.

 

👩🏻‍💻 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;

public class Main {
    static int N, K, min = Integer.MAX_VALUE, max = 100000;
    static boolean[] visited;

    public static class Node {
        int x;
        int t;

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

    public static void bfs() {
        Deque<Node> q = new ArrayDeque<>();
        q.offer(new Node(N, 0));

        while (!q.isEmpty()) {
            Node node = q.poll();
            visited[node.x] = true;
            if (node.x == K) min = Math.min(min, node.t);

            if (node.x * 2 <= max && !visited[node.x * 2]) q.offer(new Node(node.x * 2, node.t));
            if (node.x + 1 <= max && !visited[node.x + 1]) q.offer(new Node(node.x + 1, node.t + 1));
            if (node.x - 1 >= 0 && !visited[node.x - 1]) q.offer(new Node(node.x - 1, node.t + 1));
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[max + 1];

        bfs();
        System.out.println(min);

    }
}