[백준] S1 12761번 돌다리 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

12761번: 돌다리

[문제] 

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 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≤A,B≤30 이고  0≤N,M≤100,000)

[출력]

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

 

---

[풀이]

1. 값을 입력받아준다.

2. BFS 탐색을 해준다.

3. BFS 탐색에서는 이동할 수 있는 방법들을 모두 큐에 담는 방법으로 처리한다.

4. 도착지점에 도달하면 결과를 출력한다.

[접근]

 1. BFS, DFS 를 사용해서 문제를 풀면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;
	static int a, b;
	static int[] map;
	static int max = 100000; // 최대 범위

	public static void main(String[] args) throws Exception {
		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());
		
		map = new int[max + 1];
		
		bfs();
	}
	
	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(n);
		
		while (!q.isEmpty()){
			int pos = q.poll();
			
			// 동규의 현재위치가 주미의 위치라면 종료
			if (pos == m) {
				System.out.println(map[m]);
				return;
			}
			// -1칸 이동
			if (pos - 1 >= 0 && map[pos - 1] == 0) {
				map[pos - 1] = map[pos] + 1;
				q.offer(pos - 1);
			}
			// +1칸 이동
			if (pos + 1 <= max && map[pos + 1] == 0) {
				map[pos + 1] = map[pos] + 1;
				q.offer(pos + 1);
			}
			// -a칸 이동
			if (pos - a >= 0 && map[pos - a] == 0) {
				map[pos - a] = map[pos] + 1;
				q.offer(pos - a);
			}
			// +a칸 이동
			if (pos + a <= max && map[pos + a] == 0) {
				map[pos + a] = map[pos] + 1;
				q.offer(pos + a);
			}
			// -b칸 이동
			if (pos - b >= 0 && map[pos - b] == 0) {
				map[pos - b] = map[pos] + 1;
				q.offer(pos - b);
			}
			// +b칸 이동
			if (pos + b <= max && map[pos + b] == 0) {
				map[pos + b] = map[pos] + 1;
				q.offer(pos + b);
			}
			// a배 이동
			if (pos * a <= max && map[pos * a] == 0) {
				map[pos * a] = map[pos] + 1;
				q.offer(pos * a);
			}
			// b배 이동
			if (pos * b <= max && map[pos * b] == 0) {
				map[pos * b] = map[pos] + 1;
				q.offer(pos * b);
			}
		}
	}
}