[백준] 9019 DSLR - JAVA

★★☆

문제

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

9019번: DSLR

풀이시간 : 45분

풀이

1. 명령어 String과 레지스터 값이 포함된 Node 클래스를 생성한다.

2. A에서 B가 되는 최소한의 명령어를 출력해야 하기 때문에 BFS 너비 우선 탐색으로 완전 탐색을 돌면서 가장 빨리 B가 되는 Node의 명령어를 출력하면 된다.

 

첫 제출에서는 메모리 초과가 났다. visited 여부를 체크를 하지 않아서 메모리 초과가 났다!

우리는 목적 값에 가장 빠르게 도달하기만 하면 되기 때문에 똑같은 값을 두 번 방문 할 필요가 없다.

 

코드

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

/*
    DSLR
    골드 5
    시간 : 2484ms
    메모리 : 295672kb
*/

public class Main {

    /*
    D : 2n mod 10000 & n을 두배로. 결과가 10000이상인 경우 10000으로 나눈 나머지.
    S : n-1 & 0 -> 9999
    L : d2 d3 d4 d1
    R : d4 d1 d2 d3
    */
    static int a, b;
    static StringBuilder sb = new StringBuilder();
    static boolean[] v;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int t = 0; t < T; t++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            v = new boolean[10000];

            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            sb.append(bfs(a, b)).append("\n");
        }

        System.out.println(sb);
    }

    private static String bfs(int a, int b) {

        Queue<Node> queue = new LinkedList<>();

        queue.add(new Node(a, ""));
        v[a] = true;

        while (!queue.isEmpty()) {

            Node cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int tmp = 0;
                char d = '0';

                if (i == 0) {
                    tmp = (cur.value * 2) % 10000;
                    d = 'D';
                } else if (i == 1) {
                    tmp = (cur.value == 0) ? 9999 : cur.value - 1;
                    d = 'S';
                } else if (i == 2) {
                    // 1234 2341
                    tmp = (cur.value%1000) * 10 + cur.value/1000;
                    d = 'L';
                } else if (i == 3) {
                    // 1234 4123
                    tmp = (cur.value%10) * 1000 + (cur.value/10);
                    d = 'R';
                }

                if(v[tmp]) continue;

                if(tmp == b) {
                    return cur.str+d;
                }
                else{
                    queue.add(new Node(tmp,cur.str+d));
                    v[tmp] = true;
                }

            }
        }

        return "";
    }

    public static class Node {
        int value;
        String str;

        public Node(int value, String str) {
            this.value = value;
            this.str = str;
        }
    }

}