[BOJ] 9019 : DSLR (Java)

https://www.acmicpc.net/problem/9019

9019번: DSLR

걸린 시간 : 1시간 4분

---

C++에서 Java로 옮기려고 하니까 쉬운 코드여도 실수가 엄청 잦고 코드도 깔끔하게 안 써진다...

처음엔 DP로 생각하고 풀려다가,, 그냥 BFS로 밀어버려도 되겠다고 생각해서 중간에 싹 바꿨다.

자료구조

• memo배열 : 해당 인덱스까지 오려면 어떤 연산을 거쳐야 하는지에 대한 String형 배열이다.
• vis배열 : 해당 인덱스에 방문했다면 더 이상 방문하면 안된다. 첫 방문이 제일 빠른 연산일테니까 말이다.
• q : 큐가 비어있지 않으면 도착지까지 방문하지 않았을 때 BFS를 반복한다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ9019 {

    static String[] operator = {"D", "S", "L", "R"};

    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());
            int b = Integer.parseInt(st.nextToken());
            String[] memo = new String[10001];
            boolean[] vis = new boolean[10001];
            Queue<Integer> q = new LinkedList<>();
            q.offer(a);
            memo[a] = "";
            vis[a] = true;
            while (!q.isEmpty() && !vis[b]) {
                int cur = q.poll();
                for (int k = 0; k < 4; k++) {
                    int next;
                    if (k == 0)
                        next = (cur * 2) % 10000;
                    else if (k == 1)
                        next = (cur == 0) ? 9999 : cur - 1;
                    else if (k == 2)
                        next = (cur % 1000) * 10 + (cur / 1000);
                    else
                        next = (cur / 10) + (cur % 10) * 1000;

                    if (!vis[next]) {
                        vis[next] = true;
                        memo[next] = memo[cur] + operator[k];
                        q.offer(next);
                    }
                }
            }
            System.out.println(memo[b]);
        }
    }
}