[JAVA] 백준 돌다리

BFS를 활용하는 문제이다.

BFS를 활용한다면 큐를 생각해낸다.

 

그리고 while문을 사용하여 계속해서 뻗어나가는 그림을 생각하자.

import java.awt.Point;
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 int A, B, N, M, result = 0;
    static boolean[] visited = new boolean[100001];

    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());

        bfs();
        System.out.println(result);
    }

    static void bfs() {
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(N, 0));
        visited[N] = true;

        while (!queue.isEmpty()) {
            Point po = queue.poll();
            if (po.x == M) {
                result = po.y;
                return;
            }

            if (po.x + 1 < 100001 && !visited[po.x + 1]) {
                visited[po.x + 1] = true;
                queue.add(new Point(po.x + 1, po.y + 1));
            }
            if (po.x - 1 >= 0 && !visited[po.x - 1]) {
                visited[po.x - 1] = true;
                queue.add(new Point(po.x - 1, po.y + 1));
            }
            if (po.x + A < 100001 && !visited[po.x + A]) {
                visited[po.x + A] = true;
                queue.add(new Point(po.x + A, po.y + 1));
            }
            if (po.x + B < 100001 && !visited[po.x + B]) {
                visited[po.x + B] = true;
                queue.add(new Point(po.x + B, po.y + 1));
            }
            if (po.x - A >= 0 && !visited[po.x - A]) {
                visited[po.x - A] = true;
                queue.add(new Point(po.x - A, po.y + 1));
            }
            if (po.x - B >= 0 && !visited[po.x - B]) {
                visited[po.x - B] = true;
                queue.add(new Point(po.x - B, po.y + 1));
            }
            if (po.x * A < 100001 && !visited[po.x * A]) {
                visited[po.x * A] = true;
                queue.add(new Point(po.x * A, po.y + 1));
            }
            if (po.x * B < 100001 && !visited[po.x * B]) {
                visited[po.x * B] = true;
                queue.add(new Point(po.x * B, po.y + 1));
            }
        }
    }
}