문제
백준 9019번
https://www.acmicpc.net/problem/9019
네 개의 명령어 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로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 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 이 된다.
생각하기
식을 세우는 것과 BFS라는 것만 생각하면 엄청 어렵다고는 하기 힘든 문제인 것 같다.
물론 나는 다른 분들 코드를 보고 이해하고나서야 풀 수 있었다..
동작
int D() {
return (num * 2) % 10000;
}
int S() {
return num == 0 ? 9999 : num - 1;
}
int L() {
return num % 1000 * 10 + num / 1000;
}
int R() {
return num % 10 * 1000 + num / 10;
}class를 통해서 각 D, S, L, R의 return 값에 맞게 메소드를 미리 만들어 두고,
이 메소드들을 모두 돌려보면서 start과 target이 같아지면 중지하도록 설계를 하면된다.
boolean[] visit = new boolean[10000];
visit[start] = true;
que.clear();
que.offer(new Register(start, ""));
while( !que.isEmpty() ) {
Register reg = que.poll();
if(reg.num == target) {
System.out.println(reg.command);
break;
}
if(!visit[reg.D()]) {
que.offer(new Register(reg.D(), reg.command + "D"));
visit[reg.D()] = true;
}
if(!visit[reg.S()]) {
que.offer(new Register(reg.S(), reg.command + "S"));
visit[reg.S()] = true;
}
if(!visit[reg.L()]) {
que.offer(new Register(reg.L(), reg.command + "L"));
visit[reg.L()] = true;
}
if(!visit[reg.R()]) {
que.offer(new Register(reg.R(), reg.command + "R"));
visit[reg.R()] = true;
}BFS의 개념은 여기서 들어가는데, 모든 메소드 D,S,L,R을 다 실행해보면서 가장 먼저 target에 도달하는 값을 출력하면 된다.
que : (1234, )
que : (2468, D)
que : (1233, S)
que : (2341, L)
que : (4123, R)
que : (4936, DD)
que : (2467, DS)
que : (4682, DL)
que : (8246, DR)
que : (2466, SD)
que : (1232, SS)
que : (2331, SL)
que : (3123, SR)
que : (2340, LS)
que : (3412, LL)
LLque에 들어가는 값은 이런식으로 된다.
옆에 reg.command가 누적되는 값을 보면
DSLR ->DD, DS, DL, DR, SD, SS, SL,... 이런식으로
DSLR이 계속 누적된다.
그리고 정답을 찾을 수 있다.
코드
import java.util.*; import java.io.*; public class Main { static class Register { int num; String command; Register(int num, String command) { this.num = num; this.command = command; } int D() { return (num * 2) % 10000; } int S() { return num == 0 ? 9999 : num - 1; } int L() { return num % 1000 * 10 + num / 1000; } int R() { return num % 10 * 1000 + num / 10; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Queue<Register> que = new LinkedList<>(); while(N-->0) { StringTokenizer st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int target = Integer.parseInt(st.nextToken()); boolean[] visit = new boolean[10000]; visit[start] = true; que.clear(); que.offer(new Register(start, "")); while( !que.isEmpty() ) { Register reg = que.poll(); if(reg.num == target) { System.out.println(reg.command); break; } if(!visit[reg.D()]) { que.offer(new Register(reg.D(), reg.command + "D")); visit[reg.D()] = true; } if(!visit[reg.S()]) { que.offer(new Register(reg.S(), reg.command + "S")); visit[reg.S()] = true; } if(!visit[reg.L()]) { que.offer(new Register(reg.L(), reg.command + "L")); visit[reg.L()] = true; } if(!visit[reg.R()]) { que.offer(new Register(reg.R(), reg.command + "R")); visit[reg.R()] = true; } } } } // End of main } // End of class
