[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));
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}