백준 9019 - DSLR
문제
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다.
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로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.
1234 →L 2341 →L 3412
1234 →R 4123 →R 3412
따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.
n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.
입력
프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.
출력
A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.
Test Case
Input
3
1234 3412
1000 1
1 16output
LL
L
DDDD
풀이
주목해야 할 점은, A와 B 모두 (0 <= A, B < 10,000)이라는 점이다.
한 숫자에 대해서 4가의 경우의 수가 계속 생긴다. 마치 일반적인 2차원 배열 BFS문제에서 상, 하, 좌, 우의 경우를 방문하는 것처럼 해결하면 되지 않을까?
추가로 고려해야 할 점은, B(타겟)을 만들 수 있는 경우가 다양하다는 점이다. 그래서, 탐색하는 정점들마다의 연산로그 상태를 저장해야한다 (ex LL, DLSS,...) BFS탐색을 하니 B를 발견하면 최소 depth임이 보장된다는 점을 고려하여 다음과 같이 코드를 작성하였다.
DSLR 연산
public CommandStatus command(String commandType) {
int updateNumber = 0;
String updateCommandLog = this.commandLog + commandType;
if (commandType.equals("D")) {
updateNumber = commandD();
} else if (commandType.equals("S")) {
updateNumber = commandS();
} else if (commandType.equals("L")) {
updateNumber = commandL();
} else if (commandType.equals("R")) {
updateNumber = commandR();
}
return new CommandStatus(updateNumber, this.stackSize + 1, updateCommandLog);
}
private int commandD() {
int afterCommand = (this.number * 2) % 10000;
return afterCommand;
}
private int commandS() {
int afterCommand = this.number - 1;
if (afterCommand < 0) {
afterCommand = 9999;
}
return afterCommand;
}
private int commandL() {
//ex) 4231 -> 2314
int upscale = this.number * 10; //42310
int popFirst = upscale / 10000; //4
int lefts = upscale % 10000; //2310
int afterCommand = lefts + popFirst; //2314
return afterCommand;
}
private int commandR() {
//ex) 1234 -> 4123
int pop = this.number % 10; // 4
int lefts = this.number / 10; // 123
// 1000 + 100
int afterCommand = (pop * 1000) + lefts;
return afterCommand;
}기준 정점으로부터 4개의 case(D,S,L,R)을 방문해야 한다. 그래서 기준 정점의 메서드를 통해 새로운 정점을 연산하여 반환하는
public CommandStatus command(String commandType) 메서드를 만들었다.
commandD, commandS는 별로 어렵지 않지만, commandL, commandR에 대해선 자주 호출되는 연산임을 고려해 String형태로 처리하지 않고 int그대로 처리하는 아이디어를 차용했다.
BFS
CommandStatus[] commandStatusBoard = new CommandStatus[10001];
CommandStatus startNumber = new CommandStatus(A, 0, "");
commandStatusBoard[startNumber.number] = startNumber;
Deque<CommandStatus> deque = new ArrayDeque<>();
deque.add(startNumber);
while (!deque.isEmpty()) {
CommandStatus standardStatus = deque.poll();
for (int i = 0; i < 4; i++) {
if (commandStatusBoard[B] != null) {
return commandStatusBoard[B].commandLog;
}
String commandType = commandTypes[i];
CommandStatus currentStatus = standardStatus.command(commandType);
// 이미 계산했던 숫자인 경우
if (commandStatusBoard[currentStatus.number] != null
&& currentStatus.stackSize < commandStatusBoard[currentStatus.number].stackSize) {
commandStatusBoard[currentStatus.number] = currentStatus;
deque.add(currentStatus);
continue;
}
if (commandStatusBoard[currentStatus.number] == null) {
commandStatusBoard[currentStatus.number] = currentStatus;
deque.add(currentStatus);
}
}
}방문 여부를 저장하는 commandStatusBoard[]를 만들었다. A, B 모두 10000미만이므로 메모리를 미리 할당하여 접근에 유리하도록 하였다. commandStatusBoard[n]이 null인 경우에는 최초 방문이므로 그냥 저장하면 된다. 하지만, 이미 있는 경우는 최소의 케이스를 저장해야 한다. 만약 depth가 4인 상태에서 N = 100이 되었을 때, 고민없이 저장해버린다면, commandStatusBoard[100]에 depth가 1일 때 이미 저장되어있는 경우를 덮어쓰기 때문이다.
정답 코드
public class Boj_9019 {
private static String[] commandTypes = new String[] {"D", "S", "L", "R"};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
String answer = mainSolution(br);
System.out.println(answer);
}
}
private static String mainSolution(BufferedReader br) throws IOException {
String[] AB = br.readLine().split(" ");
final int A = Integer.parseInt(AB[0]);
final int B = Integer.parseInt(AB[1]);
CommandStatus[] commandStatusBoard = new CommandStatus[10001];
CommandStatus startNumber = new CommandStatus(A, 0, ""); //CommandStatus에는 숫자, depth, commandLog가 들어간다
commandStatusBoard[startNumber.number] = startNumber;
Deque<CommandStatus> deque = new ArrayDeque<>();
deque.add(startNumber);
//BFS 시작
while (!deque.isEmpty()) {
CommandStatus standardStatus = deque.poll();
for (int i = 0; i < 4; i++) { //D, S, L, R 연산
if (commandStatusBoard[B] != null) { //타겟을 찾았으면 종료
return commandStatusBoard[B].commandLog;
}
String commandType = commandTypes[i];
CommandStatus currentStatus = standardStatus.command(commandType); //명령을 통해 생성된 새로운 CommandStatus 반환
// 이미 계산했던 숫자인 경우
if (commandStatusBoard[currentStatus.number] != null
&& currentStatus.stackSize < commandStatusBoard[currentStatus.number].stackSize) {
// 이미 계산한 숫자지만, 더 적은 횟수인 경우엔 업데이트
commandStatusBoard[currentStatus.number] = currentStatus;
deque.add(currentStatus);
continue;
}
if (commandStatusBoard[currentStatus.number] == null) {
commandStatusBoard[currentStatus.number] = currentStatus;
deque.add(currentStatus);
}
}
}
return commandStatusBoard[B].commandLog;
}
}
class CommandStatus {
int number;
int stackSize;
String commandLog;
public CommandStatus(int number, int stackSize, String commandLog) {
this.number = number;
this.stackSize = stackSize;
this.commandLog = commandLog;
}
public CommandStatus command(String commandType) {
int updateNumber = 0;
String updateCommandLog = this.commandLog + commandType;
if (commandType.equals("D")) {
updateNumber = commandD();
} else if (commandType.equals("S")) {
updateNumber = commandS();
} else if (commandType.equals("L")) {
updateNumber = commandL();
} else if (commandType.equals("R")) {
updateNumber = commandR();
}
return new CommandStatus(updateNumber, this.stackSize + 1, updateCommandLog);
}
private int commandD() {
int afterCommand = (this.number * 2) % 10000;
return afterCommand;
}
private int commandS() {
int afterCommand = this.number - 1;
if (afterCommand < 0) {
afterCommand = 9999;
}
return afterCommand;
}
private int commandL() {
//ex) 4231 -> 2314
int upscale = this.number * 10; //42310
int popFirst = upscale / 10000; //4
int lefts = upscale % 10000; //2310
int afterCommand = lefts + popFirst; //2314
return afterCommand;
}
private int commandR() {
//ex) 1234 -> 4123
int pop = this.number % 10; // 4
int lefts = this.number / 10; // 123
// 1000 + 100
int afterCommand = (pop * 1000) + lefts;
return afterCommand;
}
}
