[Algo] 백준 12761 돌다리 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/12761

메모리 : 20352KB

시간 : 172ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int idx, cnt;

        Node(int idx, int cnt) {
            this.idx = idx;
            this.cnt = cnt;
        }
    }

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int ans = 0;
        int[] vector = { 1, -1, A, -1 * A, B, -1 * B };
        boolean[] check = new boolean[100001];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(N, 0));
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.idx == M) {
                ans = node.cnt;
                break;
            }
            for (int k = 0; k < 6; k++) {
                if (node.idx + vector[k] >= 0 && node.idx + vector[k] <= 100000 && !check[node.idx + vector[k]]) {
                    check[node.idx + vector[k]] = true;
                    q.add(new Node(node.idx + vector[k], node.cnt + 1));
                }
            }
            if (node.idx * A <= 100000 && !check[node.idx * A]) {
                check[node.idx * A] = true;
                q.add(new Node(node.idx * A, node.cnt + 1));
            }
            if (node.idx * B <= 100000 && !check[node.idx * B]) {
                check[node.idx * B] = true;
                q.add(new Node(node.idx * B, node.cnt + 1));
            }
        }
        System.out.println(ans);
    }

}