백준12761번 - 돌다리

 

 

 

https://www.acmicpc.net/problem/12761

12761번: 돌다리

 

문제풀이 

1. 현위치에서 한칸 왼쪽가기

2. 현위치에서 한칸 오른쪽가기

3. 현위치에서 a칸 왼쪽 가기

4. 현위치에서 a칸 오른쪽가기

5. 현위치에서 b칸 왼쪽 가기

6. 현위치에서 b칸 오른쪽가기

7. 현위치의 a배 왼쪽가기

->현위치의 a배는 무조건 값이 0보다 작게되므로 불가능 

8. 현위치의 a배 오른쪽가기

9. 현위치의 b배 왼쪽가기 

->현위치의 b배는 무조건 값이 0보다 작게되므로 불가능 

10.현위치의 b배 오른쪽가기

 

총 8가지 조건만 코드로 구현하면된다. 

 

package BOJ;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main2 {

	static int A, B, N, M;
	static int[] map = new int[100001];

	static Queue<Integer> que;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		A = sc.nextInt();
		B = sc.nextInt();
		N = sc.nextInt();
		M = sc.nextInt();

		bfs();

	}

	private static void bfs() {
		que = new LinkedList<>();
		que.add(N);
		map[N] = 1;
		while (!que.isEmpty()) {
			N = que.poll();
			if (N == M) {

				break;
			}
			if (N + 1 <= 100000 && map[N + 1] == 0) {
				que.add(N + 1);
				map[N + 1] = map[N] + 1;
			}
			if (N - 1 >= 0 && map[N - 1] == 0) {
				que.add(N - 1);
				map[N - 1] = map[N] + 1;
			}
			if (N + A <= 100000 && map[N + A] == 0) {
				que.add(N + A);
				map[N + A] = map[N] + 1;
			}
			if (N * A <= 100000 && map[N * A] == 0) {
				que.add(N * A);
				map[N * A] = map[N] + 1;
			}
			if (N - A >= 0 && map[N - A] == 0) {
				que.add(N - A);
				map[N - A] = map[N] + 1;
			}

			if (N + B <= 100000 && map[N + B] == 0) {
				que.add(N + B);
				map[N + B] = map[N] + 1;
			}
			if (N - B >= 0 && map[N - B] == 0) {
				que.add(N - B);
				map[N - B] = map[N] + 1;
			}

			if (N * B <= 100000 && map[N * B] == 0) {
				que.add(N * B);
				map[N * B] = map[N] + 1;
			}
		}
		System.out.println(map[M] - 1);

	}
}