아이디어

• 4가지 연산을 수행하는 경우를 그래프가 이어진 것으로 생각하여 풀어야 하는 문제
• 가장 연산 수가 짧은 것을 찾아야 하므로, 즉 탐색 깊이가 가장 작아야 하므로 BFS로 찾아야 한다.
  • (A ≠ B이므로) A에 각 연산을 적용한 값부터 B를 찾을 때까지 무한 반복하면 된다. 언제나 B를 찾을 수 있으니 Queue가 비게 되는 경우는 없다.
• 테스트 케이스(TC)가 몇 개인지는 모르겠지만, naive하게 구현하면 시간 초과나 메모리 초과를 얻는다. 최적화할 점을 생각해보자.
  • TC의 입력과 관계 없이 0~9999의 수에 대해 'D', 'S', 'L', 'R' 연산의 결과는 항상 일정하니 미리 구해놓으면 시간적으로 조금 더 이득일 것 같다.
  • 결과가 같으면서 더 긴 연산으로 빠지는 경우는 enqueued[] 배열이 있으니 보지 않는다.
  • 출력을 위해 BFS의 상태 변수마다 현재까지의 연산 기록을 모두 들고다니는 것은 아주 큰 낭비이다.
    • 대신, 각 상태 변수는 직전에 수행한 연산만 들고 다니고, 각 상태 변수가 이전 상태 변수의 참조를 들고 있다고 해보자.
    • 이렇게 되면 출력할 때만 상태를 역행하면서 출력을 뒤에서부터 쌓으면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;
	static StringBuilder buf = new StringBuilder();
	
	static int A, B;
    
	static final char[] NAME = {'D', 'S', 'L', 'R'};
		
    static int[][] f;
    
    static Queue<Node> q = new ArrayDeque<>();
    static boolean[] enqueued = new boolean[10000];
    
    public static void main(String[] args) throws Exception {
        f = new int[10000][4];
        for (int i=0; i<10000; i++) {
            f[i][0] = (2 * i) % 10000;
            f[i][1] = (i + 9999) % 10000;
            f[i][2] = (i % 1000) * 10 + i / 1000;
            f[i][3] = (i / 10) + (i % 10) * 1000;
        }

        int T = Integer.parseInt(rd.readLine());
        for (int t=1; t<=T; t++) {        	
        	tk = new StringTokenizer(rd.readLine());
            A = Integer.parseInt(tk.nextToken());
            B = Integer.parseInt(tk.nextToken());
            bfs();
        }
        System.out.println(sb);
    }
    
    static void bfs() {
        Arrays.fill(enqueued, false);
        q.clear();
        
        for (int i=0; i<4; i++) {
        	int x = f[A][i];
            q.add(new Node(x, i, null));
            enqueued[x] = true;
        }
        
        while (true) {
        	Node node = q.poll();
        	
        	int n = node.n;
        	if (n == B) {
        		print(node);
        		break;
        	}
        	
        	for (int i=0; i<4; i++) {
        		int x = f[n][i];
        		if (enqueued[x]) continue;
        		enqueued[x] = true;
        		q.add(new Node(x, i, node));
        	}
        }
    }
    
    static void print(Node node) {
    	buf.setLength(0);
    	while (node != null) {
    		buf.insert(0, NAME[node.op]);
    		node = node.prev;
    	}
    	sb.append(buf).append('\n');
    }

	static class Node {
		int n;
		int op;
		Node prev;
		
		Node(int n, int op, Node prev) {
			this.n = n;
			this.op = op;
			this.prev = prev;
		}
	}
}

메모리 및 시간

• 메모리: 300900 KB
• 시간: 2672 ms

리뷰

• 이 문제는 사실 예전에 풀었었는데, 아무리 생각해도 너무 비효율적이고 컨벤션도 맞지 않아 두고 볼 수 없었다. 이전 코드는 여기서 볼 수 있다. (325920 KB, 9100 ms)
• BFS의 방문 배열(enqueued[])를 새 노드를 삽입할 때 처리하면 복잡한 백트래킹 처리를 하지 않아도 된다는 사실을 뒤늦게 알았다.
• 이 문제의 시간복잡도를 더 낮추고 싶다면 bidirectional BFS에 대해 알아야 한다고 한다.
  • 말 그대로 A와 B 양방향에서 동시에 BFS를 하여 처음으로 겹치는 점이 생기면 탐색을 종료하는 방법
  • BFS의 시간복잡도는 분기 수를 $n$, 깊이를 $d$라 하면 탐색 횟수가 $O(n^d)$였는데, 차수를 절반으로 줄여 $O(n^{d/2})$로 만들 수 있다고 한다.