[백준 9019 - JAVA] DSLR

9019번: DSLR

숫자A에서 숫자B로 변환하기 위해 필요한 최소한의 명령어 나열을 구하자!

bfs에 대한 개념을 잘 잡고 있다면 간단하게 풀 수 있다.

제출 후 정답율이 올라가는게 삐끄덕 거리면서 느려서 당황했지만 무사히 통과! ✧ʕ̢̣̣̣̣̩̩̩̩·͡˔·ོɁ̡̣̣̣̣̩̩̩̩✧

 

풀이 방법

숫자와 문자열을 가진 Number클래스를 이용해 bfs를 수행한다.

1. 큐에 숫자A를 넣고 시작한다.
2. DSLR을 순차적으로 실행 후, 숫자를 비교하여 숫자B와 같을 경우 문자열을 반환한다.
3. visit배열을 확인하여 나온적있는 숫자일 경우 continue
4. 큐에 넣고 다음 사이클을 수행한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static final int MAX = 10000;
	public static int numA, numB;
	public static boolean[] v;
	public static int[] A, B;
	public static char[] order = { 'D', 'S', 'L', 'R' };

	static class Number {
		int num;
		String str;

		public Number(int num, String str) {
			this.num = num;
			this.str = str;
		}
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			v = new boolean[MAX];

			st = new StringTokenizer(br.readLine());
			numA = Integer.parseInt(st.nextToken());
			numB = Integer.parseInt(st.nextToken());

			System.out.println(bfs());
		}
	}

	private static String bfs() {
		Queue<Number> que = new LinkedList<>();
		v[numA] = true;
		que.add(new Number(numA, ""));

		while (!que.isEmpty()) {
			Number cur = que.poll();
			for (int i = 0; i < 4; i++) {
				int num = changeNumber(cur.num, i);
				if (num == numB) return cur.str+order[i];
				
				if (v[num]) continue;
				que.add(new Number(num, cur.str+order[i]));
				v[num] = true;
			}
		}
		return "";
	}

	private static int changeNumber(int cur, int idx) {
		int num = 0;
		int n, tmp;
		switch (idx) {
		case 0:
			num = (cur * 2) % MAX;
			break;
		case 1:
			num = cur - 1;
			if (num < 0)
				num = 9999;
			break;
		case 2:
			n = cur / 1000;
			tmp = cur % 1000;
			num = tmp*10 + n;
			break;
		case 3:
			n = cur % 10;
			tmp = cur / 10;
			num = tmp + n * 1000;
			break;
		}
		return num;
	}

}
​