문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는
(N)번 돌 위에, 주미는
(M)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해
(A, B) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서
(A)나
(B)만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의
(A)배나
(B)배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘
(A)와
(B), 그리고 동규의 현재위치
(N), 주미의 현재 위치
(M)이 주어진다. (단,
(2 \le A, B \le 30) 이고
(0 \le N, M \le 100,000))

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

import java.util.*;
import java.io.*;
public class Main {
    static int A, B, N, M, result;
    static int[] arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[100001];
        visited = new boolean[100001];

        BFS(N);
        System.out.println(result);


    }
    public static void BFS(int v) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(v, 0));
        visited[v] = true;
            while (!q.isEmpty()) {
                Node n = q.poll();
                int x = n.x;

                if (x - 1 >= 0 && !visited[x - 1]) {
                    visited[x - 1] = true;
                    arr[x-1] = n.cnt+1;
                    q.add(new Node(x - 1, n.cnt + 1));
                }
                if (x + 1 < 100001 && !visited[x + 1]) {
                    visited[x + 1] = true;
                    arr[x+1] = n.cnt+1;
                    q.add(new Node(x + 1, n.cnt+1));
                }
                if (x + A < 100001 && !visited[x + A]) {
                    visited[x + A] = true;
                    arr[x+A] = n.cnt+1;
                    q.add(new Node(x + A, n.cnt + 1));
                }
                if (x - A >= 0 && !visited[x - A]) {
                    visited[x - A] = true;
                    arr[x-A] = n.cnt+1;
                    q.add(new Node(x - A, n.cnt + 1));
                }
                if (x + B < 100001 && !visited[x + B]) {
                    visited[x + B] = true;
                    arr[x+B] = n.cnt+1;
                    q.add(new Node(x + B, n.cnt + 1));
                }
                if (x - B >= 0 && !visited[x - B]) {
                    visited[x - B] = true;
                    arr[x-B] = n.cnt+1;
                    q.add(new Node(x - B, n.cnt + 1));
                }
                if (x * A < 100001 && !visited[x * A]) {
                    visited[x * A] = true;
                    arr[x*A] = n.cnt+1;
                    q.add(new Node(x * A, n.cnt + 1));
                }
                if (x * B < 100001 && !visited[x * B]) {
                    visited[x * B] = true;
                    arr[x*B] = n.cnt+1;
                    q.add(new Node(x * B, n.cnt + 1));
                }
                if (arr[M] != 0) {
                    result = n.cnt+1;
                    return;
                }
        }

    }
}

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

• 노가다로 푼 문제.