[백준] 12761번 돌다리

- 문제 : https://www.acmicpc.net/problem/12761

 이동 가능한 방법이 총 8개 주어지고 방법에 맞게 동규를 이동 시키는 문제 입니다. 동규가 도착 지점까지 이동한 횟수의 최솟값을 출력하면 됩니다.

- 풀이

 처음에는 DP 방식으로 문제에 접근했습니다. 만약 앞으로만 이동할 수 있다면 DP를 이용해서 도착지점에서 가장 가까운 위치(도착지점 - 1)에서부터 값을 감소 시키며 시작지점에서 도착지점까지 이동한 횟수를 찾을 수 있다고 생각했습니다.

 그러나 뒤로 이동하는 경우에 DP를 이용해서 문제 해결이 불가능했습니다. 예를 들어서 앞으로만 이동 가능하고 도착 지점이 20이고 현재 11번째에서 20까지 갈 수 있는 최단거리를 찾으려고 할때 11과 20 사이의 위치에서 최단으로 20까지 갈 수 있는 방법 + 1을 해주면 됩니다.

 하지만 뒤로 이동이 가능하고 10에서 20까지 한번에 이동이 가능하다고 가정합시다. 그러나 19부터 1까지 최단 거리를 검사하기 때문에 11을 검사하는 시점에 10에서 20까지 최단거리가 아직 계산되지 못했습니다. 그래서 11에는 12부터 19까지 중에서 20까지 이동 가능한 최단거리 + 1의 값이 들어갈 것이고 이는 잘못된 값이 될수 있습니다.

 그래서 문제의 힌트를 확인하니 BFS를 이용해서 푸는 문제라는 것을 확인할 수 있었습니다. BFS 문제는 보통 주어진 맵에서 1칸 이동하는 방식으로 문제를 해결했는데, 이 문제는 총 8개의 이동 방법을 사용해서 문제를 해결했습니다. 단순히 배열의 row, col 값에 +1을 해주는 방식이 아닌 새로운 이동 방식만 잘 적용시켜주어 해결했습니다.

- 코드

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

public class StoneBridge {
	Scanner sc;
	Queue<Integer> q;
	int N, M, A, B;
	boolean[] visited;

	void setValues() {
		sc = new Scanner(System.in);
		q = new LinkedList<Integer>();
		visited = new boolean[100001];

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

	void solve() {
		setValues();
		int size, curPos, nextPos, ans = 0;
		boolean end = false;

		q.add(N);
		visited[N] = true;
		
		while (!q.isEmpty() && !end) {
			
			size = q.size();
			
			while (size > 0) {
				
				curPos = q.poll();
				size--;
				
				if (curPos == M) {
					System.out.println(ans);
					end = true;
					break;
				}
				
				for (int movableWay = 0; movableWay < 8; movableWay++) {
					nextPos = moveNext(movableWay, curPos);
					
					if (nextPos < 0 || nextPos > 100000) {
						continue;
					}
					
					if (visited[nextPos]) {
						continue;
					}
					
					q.add(nextPos);
					visited[nextPos] = true;
				}
			}
			ans++;
		}
	}

	int moveNext(int idx, int nowPos) {
		int nextPos = -1;
		switch (idx) {
		case 0:
			nextPos = nowPos + 1;
			break;
		case 1:
			nextPos = nowPos - 1;
			break;
		case 2:
			nextPos = nowPos + A;
			break;
		case 3:
			nextPos = nowPos - A;
			break;
		case 4:
			nextPos = nowPos + B;
			break;
		case 5:
			nextPos = nowPos - B;
			break;
		case 6:
			nextPos = nowPos * A;
			break;
		case 7:
			nextPos = nowPos * B;
			break;
		}
		return nextPos;

	}

	public static void main(String[] args) {
		StoneBridge m = new StoneBridge();
		m.solve();
	}

}