문제 설명
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
접근 방법
결론적으로 해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었으나, 처음에는 백트래킹으로 접근 했었습니다.
백트래킹으로 접근, 결과는 시간 초과
입력될 수 있는 명령어에 대한 모든 경우의 수를 고려하고자 했고, 가장 짧은 명령어를 찾기 위해 명령어 조합의 수를 첫째 자리부터 대략 100번째 자리까지(임의로 둔 것) 일일이 백트래킹을 해주도록 했습니다. 탐색 중 타겟 숫자와 동일해지는 순간 해당 명령어를 출력 시키도록 했지만, 결과는 시간 초과였습니다.
// ...
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
number = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
for (int j = 1; j < 100; j++) {
try {
calculate(0, j, number, target);
} catch (RuntimeException e) {
commands.clear();
break;
}
commands.clear();
}
// ...
private static void calculate(int depth, int cipher, int number, int target) {
if (depth == cipher) {
if (number == target) {
StringBuilder sb = new StringBuilder();
for (Character command : commands) {
sb.append(command);
}
System.out.println(sb);
throw new RuntimeException();
}
return;
}
commands.push('D');
calculate(depth + 1, cipher, d(number), target);
commands.pop();
commands.push('S');
calculate(depth + 1, cipher, s(number), target);
commands.pop();
commands.push('L');
calculate(depth + 1, cipher, l(number), target);
commands.pop();
commands.push('R');
calculate(depth + 1, cipher, r(number), target);
commands.pop();
}
백트래킹 시에 고려하지 못했었던 부분이 있었는데, 바로 방문 처리에 관한 부분이었습니다. 단순히 모든 경우의 수를 조합해준다는 생각만 했기에, 방문 처리를 별도로 하지 않았었는데, L 명령어와 R 명령어 사이에 일종의 순환이 발생하여 불필요한 탐색이 더 늘어나는 것이 시간 초과의 주 원인이었습니다.
너비 우선 탐색을 통한 접근
그리하여 동일한 숫자에 대해서는 중복 탐색하지 않도록 0 ~ 9999 숫자에 대해 방문 처리를 해주도록 했고, 타겟 숫자를 찾기 위한 가장 적은 명령어를 탐색하기에는 깊이 우선 탐색 보다는 동일한 길이에 대해 나란히 같이 탐색하는 너비 우선 탐색이 더 적합하다고 생각했습니다.
static class Number {
int number;
String commands;
public Number(int number, String commands) {
this.number = number;
this.commands = commands;
}
}
private static void calculate(int number, int target) {
boolean[] visited = new boolean[10000];
Queue<Number> numbers = new LinkedList<>();
numbers.add(new Number(number, ""));
visited[number] = true;
int newNumber;
while (!numbers.isEmpty()) {
Number n = numbers.poll();
newNumber = d(n.number);
if (newNumber == target) {
System.out.println(n.commands + "D");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "D"));
}
newNumber = s(n.number);
if (newNumber == target) {
System.out.println(n.commands + "S");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "S"));
}
newNumber = l(n.number);
if (newNumber == target) {
System.out.println(n.commands + "L");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "L"));
}
newNumber = r(n.number);
if (newNumber == target) {
System.out.println(n.commands + "R");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "R"));
}
}
}
L 연산과 R 연산 로직 개선
처음 L 연산과 R 연산을 구현했을 때는 해당 숫자를 문자로 변환시킨 다음 자리를 조정하여 다시 숫자로 변환시켜주도록 했습니다. 하지만 이러한 방법은 메모리면에서나 시간면에서나 비용이 많이 드는 비효율적인 작업이었습니다.
private static int l(int number) {
char[] n = getDigits(number);
char[] newNumber = new char[4];
newNumber[0] = n[1];
newNumber[1] = n[2];
newNumber[2] = n[3];
newNumber[3] = n[0];
return Integer.parseInt(new String(newNumber));
}
private static int r(int number) {
char[] n = getDigits(number);
char[] newNumber = new char[4];
newNumber[0] = n[3];
newNumber[1] = n[0];
newNumber[2] = n[1];
newNumber[3] = n[2];
return Integer.parseInt(new String(newNumber));
}
private static char[] getDigits(int number) {
StringBuilder sb = new StringBuilder();
int multiple = 1000;
for (int i = 0; i < 4; i++) {
if (number >= multiple) {
sb.append(number / multiple);
} else {
sb.append(0);
}
number %= multiple;
multiple /= 10;
}
return sb.toString().toCharArray();
}
좀 더 효율적인 방법을 찾던 중 다음과 같이 단순히 사칙 연산자와 % 연산자만으로 십진수 자릿수를 회전시킬 수 있었습니다.
private static int l(int number) {
return number % 1000 * 10 + number / 1000;
}
private static int r(int number) {
return number % 10 * 1000 + number / 10;
}
전체 소스 코드
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 class Number {
int number;
String commands;
public Number(int number, String commands) {
this.number = number;
this.commands = commands;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int number, target;
StringTokenizer st;
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
number = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
calculate(number, target);
}
}
private static void calculate(int number, int target) {
boolean[] visited = new boolean[10000];
Queue<Number> numbers = new LinkedList<>();
numbers.add(new Number(number, ""));
visited[number] = true;
int newNumber;
while (!numbers.isEmpty()) {
Number n = numbers.poll();
newNumber = d(n.number);
if (newNumber == target) {
System.out.println(n.commands + "D");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "D"));
}
newNumber = s(n.number);
if (newNumber == target) {
System.out.println(n.commands + "S");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "S"));
}
newNumber = l(n.number);
if (newNumber == target) {
System.out.println(n.commands + "L");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "L"));
}
newNumber = r(n.number);
if (newNumber == target) {
System.out.println(n.commands + "R");
return;
}
if (!visited[newNumber]) {
visited[newNumber] = true;
numbers.add(new Number(newNumber, n.commands + "R"));
}
}
}
private static int d(int number) {
return number * 2 % 10000;
}
private static int s(int number) {
return number == 0 ? 9999 : number - 1;
}
private static int l(int number) {
return number % 1000 * 10 + number / 1000;
}
private static int r(int number) {
return number % 10 * 1000 + number / 10;
}
}
참고 자료
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 1052] 물병 - Java (0) | 2022.09.06 |
|---|---|
| [백준 - 1011] Fly me to the Alpha Centauri - Java (0) | 2022.09.06 |
| [백준 - 1068] 트리 - Java (0) | 2022.08.17 |
| [백준 - 25332] 수들의 합 8 - Java (0) | 2022.08.11 |
| [백준 - 25331] Drop 7 - Java (2) | 2022.08.08 |