DSLR
어떤 행위가 존재하고, 이 행위들을 조합했을 때 최단시간/최소한 등을 구해야 한다면, BFS를 생각하게 됩니다.
그래프에서 정점은 어떤 상태를 나타내고, 간선은 상태의 변화를 나타내는데 BFS는 시작점에서 다른 상태까지의 최단 거리를 구하는 알고리즘이기 때문입니다.
이 문제에서는
- 10,000 미만의 십진수
- 명령어
- 최소한의 명령어
위의 조건이 있으므로, BFS를 고려할 때 생각해야될 이전 정점의 방문 여부를 저장할 공간의 크기가 10,000 이므로 충분히 고려할 수 있습니다.
이 문제에서는 최소한의 명령어를 탐색하고 어떤 명령어들로 이루어져 있는지 재구축 과정이 필요합니다. 이를 구현하는 방법은 여러가지가 있을 수 있지만, 저는 방문 정점 표시를 단순 boolean으로 true false로 표현하는게 아닌, 어떤 정점에서 왔는지 이전 정점에서 방문 여부를 기록하는 방법을 사용합니다. (사실 다른 방법을 따로 생각해 본 적은 없습니다..)
BFS는 쉽게 구현 가능할 것이고, 중요한 것은 계산의 구현인데, 저는 State 객체를 구현하여 문제를 풀었습니다.
저는 알고리즘 문제를 풀 때, 빠른 코드보다는 읽기 좋은 코드를 작성하려고 노력하는 편입니다. 그래서 코드의 길이가 다른 분들보다 긴 경우가 많습니다. 속도도 빠르지 않구요. 하지만 실제로 일을 할 때 도움이 되고자 그렇게 합니다.
public class BJ9019 {
// ...
static class State {
final int number;
final char beforeCommand;
final int beforeNumber;
final int[] digit;
public State(int number) {
this.number = number;
this.beforeCommand = COMMAND_START;
this.beforeNumber = -1;
this.digit = getDigit(number);
}
public State(int number, char beforeCommand, int beforeNumber, int[] digit) {
this.number = number;
this.beforeCommand = beforeCommand;
this.beforeNumber = beforeNumber;
this.digit = digit;
}
public State D() {
final int nextNumber = (2 * number) % 10_000;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_D, number, getDigit(nextNumber));
}
public State S() {
final int nextNumber = number == 0
? 9999
: number - 1;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_S, number, getDigit(nextNumber));
}
public State L() {
final int[] nextDigit = {
digit[1], digit[2], digit[3], digit[0],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_L, number, nextDigit);
}
public State R() {
final int[] nextDigit = {
digit[3], digit[0], digit[1], digit[2],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_R, number, nextDigit);
}
private static int[] getDigit(int num) {
final int[] nextDigit = new int[4];
for (int i = 3; i >= 0; i--) {
nextDigit[i] = num % 10;
num /= 10;
}
return nextDigit;
}
private static int getNumber(int[] digit) {
int number = 0;
for (int num: digit) {
number *= 10;
number += num;
}
return number;
}
}State 객체가 하는 일은 단순합니다. 현재 상태에서 DSLR 명령어를 실행했을 때, 그 다음 State 객체를 리턴합니다.
4자리의 숫자는 L과 R 명령어를 위해서 int[4] 배열로 보관하게 했습니다. 그리고 이 int[4] 배열과 이 배열의 int값을 서로 변환할 수 있는 메서드를 정의하였습니다.
beforeCommand는 나중에 명령어의 순서를 복구하기 위해 이 상태가 어떤 명령어에 의해 도달했는지 그 정보를 담고 있습니다.
이렇게 State 객체를 구현하고 나면, 나머지는 그냥 전형적인 BFS코드입니다.
정답
package bj.comito.codeplus.practice;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class BJ9019 {
private static final Deque<State> q = new LinkedList<>();
private static final Deque<Character> q2 = new LinkedList<>();
private static final State[] visited = new State[10_000];
private static final char COMMAND_START = '0';
private static final char COMMAND_D = 'D';
private static final char COMMAND_S = 'S';
private static final char COMMAND_L = 'L';
private static final char COMMAND_R = 'R';
public static void main(String[] args) throws Throwable {
final BufferedReader br = new BufferedReader(
new InputStreamReader(System.in), 1<<10
);
final BufferedWriter bw = new BufferedWriter(
new OutputStreamWriter(System.out), 1<<10
);
final int T = Integer.parseInt(br.readLine());
for (int ti = 0; ti < T; ti++) {
final StringTokenizer st = new StringTokenizer(br.readLine(), " ");
final int start = Integer.parseInt(st.nextToken());
final int end = Integer.parseInt(st.nextToken());
bw.write(solve(start, end));
bw.write('\n');
}
bw.flush();
bw.close();
br.close();
}
private static String solve(int start, int end) {
q.clear();
Arrays.fill(visited, null);
State s = new State(start);
q.offer(s);
visited[start] = s;
while (!q.isEmpty()) {
State cur = q.poll();
if (cur.number == end) {
break;
}
State next;
next = cur.D();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.S();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.L();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.R();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
}
return printCommands(end);
}
private static String printCommands(int end) {
State state = visited[end];
while (state.beforeCommand != COMMAND_START) {
q2.push(state.beforeCommand);
state = visited[state.beforeNumber];
}
StringBuilder sb = new StringBuilder(1<<8 + 1);
while (!q2.isEmpty()) {
sb.append(q2.pop());
}
return sb.toString();
}
static class State {
final int number;
final char beforeCommand;
final int beforeNumber;
final int[] digit;
public State(int number) {
this.number = number;
this.beforeCommand = COMMAND_START;
this.beforeNumber = -1;
this.digit = getDigit(number);
}
public State(int number, char beforeCommand, int beforeNumber, int[] digit) {
this.number = number;
this.beforeCommand = beforeCommand;
this.beforeNumber = beforeNumber;
this.digit = digit;
}
public State D() {
final int nextNumber = (2 * number) % 10_000;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_D, number, getDigit(nextNumber));
}
public State S() {
final int nextNumber = number == 0
? 9999
: number - 1;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_S, number, getDigit(nextNumber));
}
public State L() {
final int[] nextDigit = {
digit[1], digit[2], digit[3], digit[0],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_L, number, nextDigit);
}
public State R() {
final int[] nextDigit = {
digit[3], digit[0], digit[1], digit[2],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_R, number, nextDigit);
}
private static int[] getDigit(int num) {
final int[] nextDigit = new int[4];
for (int i = 3; i >= 0; i--) {
nextDigit[i] = num % 10;
num /= 10;
}
return nextDigit;
}
private static int getNumber(int[] digit) {
int number = 0;
for (int num: digit) {
number *= 10;
number += num;
}
return number;
}
}
}
undefined cat