D.S.L.R
백준 9019번 문제
https://www.acmicpc.net/problem/9019
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
1. 문제
문제
네 개의 명령어 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 이 된다.
입력
프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A와 B는 모두 0 이상 10,000 미만이다.
출력
A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.
예제 입력 1
3
1234 3412
1000 1
1 16
예제 출력 1
LL
L
DDDD
2. 풀이
■ 풀이방법
이 문제는 어떤 숫자 A를 B로 바꾸기 위한 최소한의 연산을 출력하는 것이다.
여기서 "숫자"는 항상 DSLR의 연산을 적용할 수 있으며 연산이 적용됨에 따라 다른 숫자로 변경된다.
즉 "숫자"는 항상 4개 이하의 숫자로 변경될 수 있다.
이제 "숫자"를 하나의 노드로 보고 DSLR을 다음 노드로 갈 수 있는 방법, 즉 간선이라고 하자
그럼 이 문제는 어떤 숫자 A를 B로 바꾸기 위한 최소한의 경로를 찾는 것이라고도 볼 수 있다.
따라서 이 문제는 BFS로 풀 수 있다.
다음과 같은 과정으로 문제를 해결한다.
● 각 연산 DSLR을 메서드로 구현한다.
● 문제의 조건에 따라 0부터 10000까지의 숫자와 경로를 담을 수 있는 배열을 만든다.
● BFS를 적용해서, 처음에 주어진 숫자로부터 변경 가능한 숫자와 경로를 넓이 우선순위로 탐색한다.
● 탐색한 노드의 숫자와 경로를 배열에 추가하고 탐색된 배열은 더 탐색하지 않는다(BFS로 탐색하기 때문에 처음 탐색한 숫자와 경로가 해당 숫자로 변경되기 위한 최소 연산(최단 경로)이다.).
● 위의 작업을 배열에 목표 숫자가 탐색될 때까지 반복한다.
■ 코드
□ DSLR 연산
[DSLR 연산]
public static int D(int n) {
return (2 * n) % 10000;
}
public static int S(int n) {
if (n == 0) {
return 9999;
}
return n - 1;
}
public static int L(int n) {
int first = n / 1000;
int sub = (n % 1000);
return (sub * 10) + first;
}
public static int R(int n) {
int end = n % 10;
int sub = n / 10;
return (end * 1000) + sub;
}문제의 조건에 따라 각 연산 DSLR을 구현하였다.
※ 123에 L을 적용하면 231이 아니라 1230이 돼야 된다. 무조건 숫자를 4자리로 인식하고 빈자리를 0으로 채우는 방식 123 => 0123
□ Node
[Node]
public static class Node {
int number;
String root;
public Node(int number, String root) {
this.number = number;
this.root = root;
}
}노드는 연산에 의해 변경된 "숫자"와 처음 숫자에서부터 해당 노드까지의 "경로"를 갖고 있어야 한다.
□ 입력, 초기화
[입력, 초기화]
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int total = scanner.nextInt();
for (int i = 0; i < total; i++) { //[1]
int start = scanner.nextInt(); //[2]
int target = scanner.nextInt();
Node[] nodes = new Node[10000 + 1]; //[3]
Queue<Node> queue = new LinkedList<>(); //[4]
.
.
.
}
}● [1] : 전체 케이스 횟수를 입력받고 그 횟수만큼 반복문을 돌린다.
● [2] : 초기값과 최종 값을 입력받는다.
● [3] : BFS 적용 시 탐색이 끝난 노드들을 확인할 배열 nodes를 초기화한다.
● [4] : BFS 적용시 사용할 Queue를 초기화한다.
□ BFS, 출력
[BFS, 출력]
public static void main(String[] args) {
.
.
.
for (int i = 0; i < total; i++) {
.
.
.
nodes[start] = new Node(start, ""); //[1]
queue.offer(nodes[start]);
while (!queue.isEmpty() || nodes[target] == null) { //[2]
Node node = queue.poll();
int d = D(node.number); //[3]
int s = S(node.number);
int l = L(node.number);
int r = R(node.number);
if (nodes[d] == null) { //[4]
nodes[d] = new Node(d, node.root + "D");
queue.offer(nodes[d]);
}
if (nodes[s] == null) {
nodes[s] = new Node(s, node.root + "S");
queue.offer(nodes[s]);
}
if (nodes[l] == null) {
nodes[l] = new Node(l, node.root + "L");
queue.offer(nodes[l]);
}
if (nodes[r] == null) {
nodes[r] = new Node(r, node.root + "R");
queue.offer(nodes[r]);
}
}
System.out.println(nodes[target].root); //[5]
}
}● [1] : 주어진 초기값을 노드로 생성하고, 노드 배열에서 숫자와 같은 인덱스에 해당 노드를 넣는다.
● [2] : Queue가 비거나(탐색할 노드가 없음), 최종 값이 탐색(nodes[target] != null)되면 반복문을 종료한다.
● [3] : 현재 노드의 숫자에 각 연산을 적용한 값(다음 노드의 숫자)을 구한다.
● [4] : 연산된 숫자의 노드가 탐색되지 않았다면, [연산된 숫자]와 [현재 노드의 경로에 연산을 추가]한 노드를 생성해서 nodes 배열에 추가한다.
● [5] : nodes에서 탐색된 최종 값 노드(nodes[target])의 경로(최단 경로)를 출력
□ 전체 코드
[전체 코드]
public class Main {
public static int D(int n) {
return (2 * n) % 10000;
}
public static int S(int n) {
if (n == 0) {
return 9999;
}
return n - 1;
}
public static int L(int n) {
int first = n / 1000;
int sub = n % 1000;
return (sub * 10) + first;
}
public static int R(int n) {
int end = n % 10;
int sub = n / 10;
return (end * 1000) + sub;
}
public static class Node {
int number;
String root;
public Node(int number, String root) {
this.number = number;
this.root = root;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int total = scanner.nextInt();
for (int i = 0; i < total; i++) {
int start = scanner.nextInt();
int target = scanner.nextInt();
Node[] nodes = new Node[10000 + 1];
Queue<Node> queue = new LinkedList<>();
nodes[start] = new Node(start, "");
queue.offer(nodes[start]);
while (!queue.isEmpty() || nodes[target] == null) {
Node node = queue.poll();
int d = D(node.number);
int s = S(node.number);
int l = L(node.number);
int r = R(node.number);
if (nodes[d] == null) {
nodes[d] = new Node(d, node.root + "D");
queue.offer(nodes[d]);
}
if (nodes[s] == null) {
nodes[s] = new Node(s, node.root + "S");
queue.offer(nodes[s]);
}
if (nodes[l] == null) {
nodes[l] = new Node(l, node.root + "L");
queue.offer(nodes[l]);
}
if (nodes[r] == null) {
nodes[r] = new Node(r, node.root + "R");
queue.offer(nodes[r]);
}
}
System.out.println(nodes[target].root);
}
}
}
댓글