백준 [9019] DSLR (JAVA)

 

문제

풀이

DSLR에 대한 연산 방법은 구했지만 명령어를 저장할 때에 그냥 모든 문자열을 이어붙이면 시간초과가 날 것 같아서 계속 고민하다가 블로그 풀이를 참고 했었는데 그냥 그대로 String 배열에 이어 붙인 것을 보고 바로 구현을 해보았다.

 

• 가장 최소 연산을 찾아야 하므로 처음 시작하는 수에서 시작한다.
• 방문 배열 v와 명령어를 저장할 cmd 배열을 선언한다.
• 시작점 부터 D, S, L, R 연산을 한 결과 값을 계속 갱신하면서 BFS 탐색을 진행한다.
• 방문한 배열이라면 큐에 저장하지 않고 계속 진행한다.
• 가장 먼저 B에 도달하는 명령어가 최소 명령어가 된다.

정답 코드

package com.baekjoon.graphs.p9019;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            ArrayDeque<Integer> Q = new ArrayDeque<>();
            boolean[] v = new boolean[10000];
            String[] cmd = new String[10000];

            Arrays.fill(cmd, "");
            Q.add(A);
            v[A] = true;

            while (!Q.isEmpty() && !v[B]) {
                int now = Q.poll();

                int D = (2 * now) % 10000;
                int S = now == 0 ? 9999 : now - 1;
                int L = (now % 1000) * 10 + now / 1000;
                int R = (now % 10) * 1000 + now / 10;

                if (!v[D]) {
                    v[D] = true;
                    Q.add(D);
                    cmd[D] = cmd[now] + "D";
                }
                if (!v[S]) {
                    v[S] = true;
                    Q.add(S);
                    cmd[S] = cmd[now] + "S";
                }
                if (!v[L]) {
                    v[L] = true;
                    Q.add(L);
                    cmd[L] = cmd[now] + "L";
                }
                if (!v[R]) {
                    v[R] = true;
                    Q.add(R);
                    cmd[R] = cmd[now] + "R";
                }
            }

            sb.append(cmd[B] + "\n");
        }

        System.out.println(sb);

    }

}