BOJ 9019 DSLR(Java)
문제 탐색하기
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다.
각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)
D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다.
예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.
주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램을 작성하여라.
입력
- 프로그램 입력은 T 개의 테스트 케이스로 구성된다.
- 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다.
- 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다.
- A 와 B는 모두 0 이상 10,000 미만이다.
출력
- A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.
예제
# 입력
3
1234 3412
1000 1
1 16
# 출력
LL
L
DDDD
코드 설계하기
구현 방법
- BFS 사용
- 큐에 현재 값의 레지스터와 결과 명령어 배열 값을 저장한다.
- 전체 가능한 명령어 셋을 수행하면서 큐에 넣는다.
- 큐에 넣은 값이 타겟 값과 같으면 큐에서 꺼낸 값의 결과 명령어 배열 값을 출력한다.
명령어 셋을 수행하는 함수 changeRegister는 레지스터 값과 명령어를 받아서 명령어에 따라 레지스터 값을 변환한다.
시간 복잡도
- 최악의 경우 시간 복잡도: O(10000)
- 레지스터는 0부터 9999까지의 값만 가질 수 있다.
- 각 숫자는 최대 한 번만 방문할 수 있다. (
visited배열로 관리) - 각 노드에서 4가지 연산(D, S, L, R)을 수행하지만, 이는 상수 시간이므로 무시할 수 있다.
- 공간 복잡도: O(10000)
visited배열이 10000개의 boolean 값을 저장한다.- 큐에 저장되는 노드의 최대 개수도 10000개를 넘지 않는다.
정답 코드 (Java)
package BFS;
import java.io.*;
import java.util.*;
public class b9019 {
static char[] command = {'D', 'S', 'L', 'R'};
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
for(int i = 0; i < t; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
visited = new boolean[10000];
// BFS 사용
bw.write(bfs(start, target) + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static String bfs(int start, int target) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(start, ""));
visited[start] = true;
while(!q.isEmpty()) {
Node current = q.poll();
if(current.register == target) return current.result;
for(int i = 0; i < 4; i++) {
int change = changeRegister(current.register, command[i]);
if(!visited[change]) {
visited[change] = true;
q.offer(new Node(change, current.result + command[i]));
}
}
}
return "";
}
public static int changeRegister(int register, char command) {
switch (command) {
case 'D':
register *= 2;
if(register > 9999) register %= 10000;
break;
case 'S':
register -= 1;
if(register == -1) register = 9999;
break;
case 'L':
int temp1 = (register % 1000) * 10;
int temp2 = register / 1000;
register = temp1 + temp2;
break;
case 'R':
int tmp1 = register / 10;
int tmp2 = (register % 10) * 1000;
register = tmp1 + tmp2;
break;
default:
break;
}
return register;
}
public static class Node {
int register;
String result;
public Node(int register, String result) {
this.register = register;
this.result = result;
}
}
}
Leave a comment