[BaekJoon] 9019 DSLR (Java)

1.  문제 링크

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

2.  문제

요약

• 네 개의 명령어 D, S, L, R을 이용하는 간단한 계산기가 있는데 이 계산기에는 레지스터가 하나 있고, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있습니다.
• 각 명령어는 레지스터에 저장된 n을 다음과 같이 변환합니다. n의 네 자릿수를 $d_1$, $d_2$, $d_3$, $d_4$라고 합니다.(n = (($d_1$ * 10 + $d_2$) × 10 + $d_3$) + $d_4$)
  1. D: D는 n을 두 배로 바꿉니다. 결과값이 9999보다 큰 경우에는 10000으로 나눈 나머지를 취합니다.(2n mod 10000)
  2. S: S는 n에서 1을 뺀 결과 n - 1을 레지스터에 저장합니다. 만약 n이 0이라면 9999를 저장합니다.
  3. L: L은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장합니다.($d_2$, $d_3$, $d_4$, $d_1$)
  4. R: R은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장합니다.($d_4$, $d_1$, $d_2$, $d_3$)
• L과 R 명령어는 십진 자릿수를 가정하고 연산을 수행합니다.
• 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지며 각 테스트 케이스는 두 개의 정수 A와 B로 이루어져 있습니다. A는 레지스터의 초기값을 나타내고 B는 최종값을 나타내며, A와 B는 모두 0 이상 10,000 미만입니다.
• 출력: A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static boolean[] visited;
	static void input() {
		Reader scanner = new Reader();
		int test_num = scanner.nextInt();
		for(int test = 1; test <= test_num; test++) {			
			int A = scanner.nextInt();
			int B = scanner.nextInt();
			visited = new boolean[10000];
			bfs(A, B);
		}
	}
	
	static void bfs(int A, int B) {
		char[] operators = {'D', 'S', 'L', 'R'};
		Queue<Process> processes = new LinkedList<Process>();
		processes.add(new Process(A, ""));
		visited[A] = true;
		while(!processes.isEmpty()) {
			Process cur_pro = processes.poll();
			if(cur_pro.num == B) {
				sb.append(cur_pro.operation).append('\n');
				break;
			}
			for(int oper = 0; oper < operators.length; oper++) {
				int result = cur_pro.num;
				if(operators[oper] == 'D') {
					result = operateD(cur_pro.num);
				} else if(operators[oper] == 'S') {
					result = operateS(cur_pro.num);
				} else if(operators[oper] == 'L') {
					result = operateL(cur_pro.num);
				} else if(operators[oper] == 'R') {
					result = operateR(cur_pro.num);
				}
				if(!visited[result]) {
					visited[result] = true;
					processes.offer(new Process(result, cur_pro.operation + operators[oper]));
				}
			}
		}
	}
	
	static int operateD(int num) {
		if(num == 0) return 0;
		int result = num * 2;
		if(result > 9999) result %= 10000;
		return result;
	}
	
	static int operateS(int num) {
		if(num == 0) return 9999;
		return num - 1;
	}

	static int operateL(int num) {
		int first_num = num / 1000;
		int result = (num - first_num * 1000) * 10 + first_num;
		return result;
	}
	
	static int operateR(int num) {
		int last_num = num % 10;
		int result = last_num * 1000 + (num / 10);
		return result;
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Process {
		int num;
		String operation;
		public Process(int num ,String operation) {
			this.num = num;
			this.operation = operation;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 각 테스트 케이스마다 BFS를 이용하여 A를 B로 바꾸는데 이 때 계산하여 나온 숫자들이 이전에 등장했었는지를 나타내는 2차원 배열 visited를 각 테스트 케이스마다 생성해줍니다.
• BFS 탐색 시에 Process 클래스를 생성하여 이용하는데 이 클래스는 숫자인 num과 이 숫자가 나오기까지 어떤 연산이 이루어졌는지를 나타내는 operation으로 이루어져있습니다.

bfs 함수

• 주어진 네 개의 명령어를 operators라는 배열에 넣고 BFS 탐색 시에 어떤 것을 탐색할지 담는 Queue를 하나 생성합니다.
• Queue에 주어진 숫자 A를 담고 A의 visited 값을 true로 변경합니다.
• Queue가 비워지기 전까지 D, S, L, R 연산들을 각 숫자에 대해 진행하며 A를 B로 변경합니다.
  * Queue에서 현재 탐색할 숫자를 뽑아 cur_pro에 담고 만약 이 숫자가 B와 같다면 A를 B로 변경하였으니 지금까지 진행해온 연산을 나타내는 cur_pro.operation을 출력하고 다음 테스트 케이스를 진행합니다.
  • 만약 B가 아니라면 현재 탐색하는 숫자에 대해 D, S, L, R 연산을 각각 하여 결과를 내보고 이 결과가 아직 BFS 탐색 시에 등장하지 않은 숫자라면 해당 숫자를 Queue에 넣어 이후에 탐색합니다.