[백준 9019] DSLR (Java)

이 문제는 시간 제한이 6초로 널널하다. 그래서 모든 경우를 따져보면 될 것 같다. 하지만, 모든 경우를 따지면 시간복잡도가 $O(N^4)$가 되므로 시간초과가 발생한다.

문제에서 명령어가 여러가지이면 아무거나 출력하라고 했으므로, BFS로 최단 경로로 접근하되 방문여부를 고려하도록 코드를 짜면 최적화가 될 것이다.

하지만, 문자열을 매번 연결하는 연산을 하면 오버헤드가 심하므로 배열을 두고 경로를 역추적하도록 코드를 작성하면 이를 해결할 수 있다.

이를 코드로 옮기면 다음과 같다.

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

public class Main {
    static int[] parent = new int[10000];
    static char[] how = new char[10000];
    static boolean[] visited = new boolean[10000];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()), B = Integer.parseInt(st.nextToken());
            Queue<Integer> q = new ArrayDeque<>();
            
            Arrays.fill(visited, false);
            visited[A] = true;
            q.add(A);
            parent[A] = -1;
            
            while (!q.isEmpty()) {
                int now = q.poll();
                if (now == B) {
                    break;
                }
                int[] next = {d(now), s(now), l(now), r(now)};
                char[] cmd = {'D', 'S', 'L', 'R'};
                for (int i = 0; i < 4; i++) {
                    if (!visited[next[i]]) {
                        visited[next[i]] = true;
                        parent[next[i]] = now;
                        how[next[i]] = cmd[i];
                        q.add(next[i]);
                    }
                }
            }
            
            StringBuilder path = new StringBuilder();
            int cur = B;
            while (parent[cur] >= 0) {
                path.append(how[cur]);
                cur = parent[cur];
            }
            path.reverse();
            System.out.println(path.toString());
        }
    }
    
    private static int d(int n) {
        return n * 2 % 10000;
    }
    
    private static int s(int n) {
        if (n == 0) return 9999;
        return n - 1;
    }
    
    private static int l(int n) {
        return (n % 1000) * 10 + n / 1000;
    }
    
    private static int r(int n) {
        return n / 10 + n % 10 * 1000;
    }
}