[백준(Baekjoon)][자바(java)] 9019 : DSLR / 동적 계획법과 최단거리 역추적

 

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

9019번: DSLR

 

문제 풀이

 

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

public class Main {
	
	static class Num {
		int num; String cmd;
		public Num(int num, String cmd) {
			this.num = num;
			this.cmd = cmd;
		}
	}

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st; int A, B;
		StringBuilder sb = new StringBuilder();
		Queue<Num> queue; Num number;
		int num, num_next, DSLR[] = new int[4], i;
		char c[] = {'D', 'S', 'L', 'R'}; String cmd;
		boolean visited[];
		loop:
		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			visited = new boolean[10000];
			queue = new LinkedList<>(); 
			queue.add(new Num(A, ""));
			while(!queue.isEmpty()) {
				number = queue.remove();
				num = number.num; cmd = number.cmd;
				if (num == B) {
					sb.append(cmd + "\n");
					continue loop;
				}
				DSLR[0] = num * 2 % 10000;				// D
				DSLR[1] = num == 0 ? 9999 : num - 1;		// S
				DSLR[2] = num % 1000 * 10 + num / 1000;	// L
				DSLR[3] = num % 10 * 1000 + num / 10;	// R
				for (i = 0; i < 4; ++i) {
					num_next = DSLR[i];
					if (!visited[num_next]) {
						queue.add(new Num(num_next, cmd + c[i]));
						visited[num_next] = true;
					}
				}
			}
		}
		br.close();
		System.out.print(sb.toString());
	}
}

아 네 자리구나