9019번: DSLR

• 레지스터에는 0 이상 10,000 미만의 숫자를 저장할 수 있다.
• 4개의 명령어(D, S, L, R)를 사용하는 계산기가 있다.
• 각 명령어의 기능:
  D: 현재 값을 2배로 만들고 10000으로 나눈 나머지를 저장
  S: 현재 값에서 1을 뺌 (0이면 9999가 됨)
  L: 각 자릿수를 왼쪽으로 회전
  R: 각 자릿수를 오른쪽으로 회전
• 두 정수 A와 B가 주어질 때, A를 B로 변환하는 최소한의 명령어 조합을 찾는다.
• 가능한 명령어 조합이 여러 개면 아무거나 출력한다.

접근

A -> B 로의 최단 경로

A에서 B로의 최단 경로를 찾는 문제다.
비슷한 문제를 풀어본 경험을 바탕으로 떠올린 풀이방법은 두가지였다.

1. DFS + 백트래킹
   재귀를 활용한 깊이 우선 탐색을 할 경우, 특정 명령어가 먼저 연속으로 사용된다. 따라서 특정 숫자에 도달했을 때, 명령어가 최소 길이라는 보장이 없다. 그렇기에 명령어의 길이를 확인하면서 갱신 시켜주어야한다는 단점이 존재한다.
   여러번 연산이 이루어지기에 DFS + 메모이제이션으로 연산의 최소화가 불가능하다고 판단했다.

2. BFS + 다익스트라
   너비 우선 탐색을 할 경우, 큐에 들어가는 명령어의 숫자가 짧은 순으로 정렬할 수 있다. 따라서 특정 숫자에 도달했을 때 사용된 명령어의 길이가 최소라는 것을 보장할 수 있다.
   게다가 레지스터에 들어가는 숫자가 4자리로 제한되기에 주어진 메모리 내에서 방문체크가 가능하다. 그렇기에 너비 우선 탐색의 최대 연산 회수는 4자리 수만큼인 10000회로 제한된다.

구현

너비 우선 탐색을 사용한다고 생각했을 때, 남은 것은 명령어를 구성하는 방법이다.

1. 명령어 연결
   다익스트라 방식에서 이전 명령어에 현재 명령어를 이어붙이고 명령어 길이 순으로 정렬한다.
   다만, 이 방식은 비효율적인 자바의 String 조작 방식을 사용하기 때문에 많이 느리다.
2. 이전 숫자 기억
   특정 숫자가 되었다면 그 숫자를 만들었던 원본 숫자를 저장한다.
   예를 들어 D를 수행할 때, 12 -> 24로 변화된다면 24의 이전 숫자는 12가 된다.
   그리고 이전 숫자는 방문체크로 인해 한번 할당되면 변화하지 않는다.
   따라서 이전 숫자와 특정 숫자를 만들 때 사용된 명령어를 저장하면, 이전 숫자를 순차적으로 찾아가면서 사용된 명령어를 확인할 수 있다.

코드

명령어 연결 방식

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(in.readLine());
        
        for(int i = 0; i < T; i++) {
        	input(in);
        	solve();        	
        }
        
    }
    
    static int from;
    static int to;
    static void input(BufferedReader in) throws IOException {
    	StringTokenizer tokens = new StringTokenizer(in.readLine());
    	from = Integer.parseInt(tokens.nextToken());
    	to = Integer.parseInt(tokens.nextToken());
    }
    
    static void solve() {
    	
    	boolean[] visited = new boolean[10_000];
    	PriorityQueue<Command> pq = new PriorityQueue<>();
    	
    	visited[from] = true;
    	pq.add(new Command(from, ""));
    	
    	
    	
    	while(!pq.isEmpty()) {
    		Command cur = pq.poll();
    		
    		if(cur.num == to) {
    			System.out.println(cur.str);
    			break;
    		}
    		
    		// D
    		int d = (cur.num * 2) % 10_000;
    		if(!visited[d]) {
    			visited[d] = true;
    			pq.add(new Command(d, cur.str + "D"));
    		}
    		
    		// S
    		int s = cur.num > 0 ? cur.num-1 : 9999;
    		if(!visited[s]) {
    			visited[s] = true;
    			pq.add(new Command(s, cur.str + "S"));
    		}
    		
    		// L
    		int top = cur.num / 1_000;
    		int l = ((cur.num * 10) % 10_000) + top;
    		if(!visited[l]) {
    			visited[l] = true;
    			pq.add(new Command(l, cur.str + "L"));
    		}
    		
            // R
    		int bottom = cur.num % 10;
    		int r = (cur.num / 10) + bottom * 1_000;
    		if(!visited[r]) {
    			visited[r] = true;
    			pq.add(new Command(r, cur.str + "R"));
    		}
    	}
    }
    
    static class Command implements Comparable<Command>{
    	int num;
    	String str;
    	
    	public Command(int num, String str) {
    		this.num = num;
    		this.str = str;
    	}
    	
    	public int compareTo(Command other) {
    		return Integer.compare(this.str.length(), other.str.length());
    	}
    }
}

이전 숫자 기억 방식

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(in.readLine());
        
        for(int i = 0; i < T; i++) {
        	input(in);
        	solve();        	
        }
        
    }
    
    static int from;
    static int to;
    static void input(BufferedReader in) throws IOException {
    	StringTokenizer tokens = new StringTokenizer(in.readLine());
    	from = Integer.parseInt(tokens.nextToken());
    	to = Integer.parseInt(tokens.nextToken());
    }
    
    static void solve() {
    	
    	boolean[] visited = new boolean[10_000];
    	int[] prev = new int[10_000];
    	char[] cmd = new char[10_000];
    	ArrayDeque<Integer> pq = new ArrayDeque<>();
    	
    	visited[from] = true;
    	pq.add(from);
    	prev[from] = -1;
    	
    	while(!pq.isEmpty()) {
    		int cur = pq.poll();
    		
    		if(cur == to) {
    			StringBuilder str = new StringBuilder();
    			int pivot = cur;
    			while(pivot != from) {
    				str.append(cmd[pivot]);
    				pivot = prev[pivot];
    			}
    			str.reverse(); // 역순으로 거슬러 올라가기에 뒤집어주어야한다.
    			System.out.println(str.toString());
    			
    			break;
    		}
    		
    		// D
    		int d = (cur * 2) % 10_000;
    		if(!visited[d]) {
    			visited[d] = true; // 방문 체크
    			prev[d] = cur; // 이전 숫자 저장
    			cmd[d] = 'D'; // 사용된 명령어 저장
    			pq.add(d);
    		}
    		
    		// S
    		int s = cur > 0 ? cur-1 : 9999;
    		if(!visited[s]) {
    			visited[s] = true;
    			prev[s] = cur;
    			cmd[s] = 'S';
    			pq.add(s);
    		}
    		
    		// L
    		int top = cur / 1_000;
    		int l = ((cur * 10) % 10_000) + top;
    		if(!visited[l]) {
    			visited[l] = true;
    			prev[l] = cur;
    			cmd[l] = 'L';
    			pq.add(l);
    		}
    		
    		// R
    		int bottom = cur % 10;
    		int r = (cur / 10) + bottom * 1_000;
    		if(!visited[r]) {
    			visited[r] = true;
    			prev[r] = cur;
    			cmd[r] = 'R';
    			pq.add(r);
    		}
    	}
    }
}

회고

• 역시나 String을 사용한 코드가 수행시간이 4배 가량 더 오래 걸렸다. 자바에서 String을 연산자로 더하는 방식은 피해야하는게 맞다.
• 습관적으로 우선순위큐를 사용하였지만, 너비우선 탐색이면서 명령어의 길이가 1로 동일하기 때문에 연산자의 길이 순으로 우선순위 정렬이 필요 없다. 따라서 이전 숫자를 기억하는 방식으로 진행했을 때, 우선순위 큐를 사용하지 않아도 되는 것이다.