[백준 9019번 / Java] DSLR

최단거리와 비슷하게 가장 짧은 명령어를 구하는 문제이기 때문에 bfs로 구현했다.

구현자체는 어렵지 않았지만 시간초과가 걸렸다 ㅠㅠ

처음에는 맵을 써서 방문을 처리할까 고민했는데 map은 삽입시 정렬 시간이 걸리는 반면 N의 값이 10000을 넘지 않기 때문에 배열을 이용하여 O(1)의 복잡도로 사용하는게 빠르다고 생각했다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] visited;

    static class Node {
        int n;
        int d1;
        int d2;
        int d3;
        int d4;
        StringBuilder command;

        Node(int d1, int d2, int d3, int d4, StringBuilder command) {
            this.n = ((d1 * 10 + d2) * 10 + d3) * 10 + d4;
            this.d1 = d1;
            this.d2 = d2;
            this.d3 = d3;
            this.d4 = d4;
            this.command = command;
        }

        Node(int n, StringBuilder command) {
            this.n = n;
            this.d1 = n / 1000;
            this.d2 = (n % 1000) / 100;
            this.d3 = (n % 100) / 10;
            this.d4 = n % 10;
            this.command = command;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            visited = new int[10000];
            bfs(A, B);
        }

    }

    private static void bfs(int A, int B) {
        Queue<Node> queue = new LinkedList<>();

        queue.add(new Node(A, new StringBuilder("")));
        visited[A] = 1;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.n == B) {
                System.out.println(cur.command);
                break;
            }

            Node tmp = D(cur);
            if(visited[tmp.n] == 0) {
                visited[tmp.n] = 1;
                queue.add(tmp);
            }

            tmp = S(cur);
            if(visited[tmp.n] == 0) {
                visited[tmp.n] = 1;
                queue.add(tmp);
            }

            tmp = L(cur);
            if(visited[tmp.n] == 0) {
                visited[tmp.n] = 1;
                queue.add(tmp);
            }
            tmp = R(cur);
            if(visited[tmp.n] == 0) {
                visited[tmp.n] = 1;
                queue.add(tmp);
            }
        }
    }

    private static Node D(Node cur) {
        int n = cur.n * 2 > 9999 ? (cur.n * 2) % 10000 : cur.n * 2;
        return new Node(n, new StringBuilder(cur.command).append("D"));
    }

    private static Node S(Node cur) {
        int n = cur.n == 0 ? 9999 : cur.n - 1;
        return new Node(n, new StringBuilder(cur.command).append("S"));
    }

    private static Node L(Node cur) {
        return new Node(cur.d2, cur.d3, cur.d4, cur.d1, new StringBuilder(cur.command).append("L"));
    }

    private static Node R(Node cur) {
        return new Node(cur.d4, cur.d1, cur.d2, cur.d3, new StringBuilder(cur.command).append("R"));
    }
}