[Java] 백준 12761번 : 돌다리

문제

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

입력

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

출력

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

예제 입력 1

2 3 1 20

예제 출력 1

4

예제 입력 2 

3 7 2 98500

예제 출력 2

10

 

소스코드

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 {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int A, B, N, M, cnt;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		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());
		
		cnt=0;
		bfs(N, M);
		System.out.println(cnt);
	}

	private static void bfs(int n, int m) {
		Queue<Integer> queue=new LinkedList<>();
		queue.add(n);
		
		boolean[] visited=new boolean[100001];
		visited[n]=true;
		int []dx= {-1,1,-1*A, A, -1*B, B};	// 이동하는 경우의 수 (A배, B배는 따로 처리해줌)
		
		while(!queue.isEmpty()) {
			int size=queue.size();
			
			while(size-->0) {
				int q=queue.poll();
				
				if(q==m) return;	// 가장 먼저 m이 되는 경우가 최소의 이동 횟수일 때가 됨
				for(int d=0;d<6;d++) {
					int nx=q+dx[d];
					if(isIn(nx) && !visited[nx]) {
						visited[nx]=true;
						queue.add(nx);
					}
				}
				
				int a=q*A;
				int b=q*B;
				if(isIn(a) && !visited[a]) {	// A배 점프하는 경우
					visited[a]=true;
					queue.add(a);
				}
				if(isIn(b) && !visited[b]) {	// B배 점프하는 경우
					visited[b]=true;
					queue.add(b);
				}
			}
			cnt++;
		}
	}
	
	private static boolean isIn(int x) {
		return x>=0 && x<=100000;
	}
}

최소 이동 횟수를 구해야하므로 bfs를 이용하여 탐색하였습니다.