[#알고리즘/BFS&Queue/[백준]9019번: DSLR(java)]

📘 Question

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

💡 Solution

BFS와 큐를 사용하여 문제를 해결한다.

💡 Code

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

public class BOJ_9019 {
	static int T, A, B;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i ++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			Queue<Integer> q = new LinkedList<>();
			String[] answer = new String[10000];
			boolean[] visited = new boolean[10000];
			
			q.add(A);
			visited[A] = true;
			Arrays.fill(answer, "");
			
			while(!q.isEmpty() && !visited[B]) {
				int now = q.poll(); 
				
				int D = (2 * now) % 10000; 
				int S = now == 0 ? 9999 : now - 1; 
				 // ex) 1234 -> 2341 
				int L = (now % 1000) * 10 + now / 1000;
				// ex) 1234 -> 4123
				int R = (now % 10) * 1000 + now / 10; 
				
				if(!visited[D]) {
					q.add(D);
					visited[D] = true;
					answer[D] = answer[now] + "D";
				}
				
				if(!visited[S]) {
					q.add(S);
					visited[S] = true;
					answer[S] = answer[now] + "S";
				}
				
				if(!visited[L]) {
					q.add(L);
					visited[L] = true;
					answer[L] = answer[now] + "L";
				}
				
				if(!visited[R]) {
					q.add(R);
					visited[R] = true;
					answer[R] = answer[now] + "R";
				}
				
			}
			System.out.println(answer[B]);
		}

	}

}