백준 9019 DSLR Java

완전 탐색으로 가능한 문제인 DSLR 문제이다. 정답률은 난이도에 비해 많이 낮은 것 같은 21%이다.

쉽다는 말은 아니다.. 

이 문제는 

n과 m이 주어졌을 때

n에서 m으로 가는 최소한의 명령어를 출력하면 된다.

 

최소한의 명령어이고

가중치가 따로 없고 

크기도 그렇게 크지 않으므로

BFS탐색으로 정말 탐색하면 풀 수 있는 문제이다.

 

처음엔 시간 초과가 나왔었는데 L과 R 명령어를 처리할 때

문자열로 처리해서 시간 초과가 나왔던 것 같다.

뭔가 저런 자릿수를 바꾸는 구현은 문자열로 하는 습관이 있는데

고쳐야겠다.

 

이 문제를 내가 헤맨이유는

명령어를 똑바로 구현하지 못했기 때문이다.

꼭 명령어를 천천히 읽어보고 구현해야 할 것 같다.

내가 잘못 이해했던 부분은

 

S: S는 n에서 1을 뺀 결과 n-1을 레지스터에 저장한다. n이 0이라면 9999 가 대신 레지스터에 저장된다.

-> n에서 1을 뺐을 때 0이면 9999가 저장되는 줄 알았는데 아니었다.

처음부터 n의 값이 0이면 9999가 저장되면 되는 것이다.

 

L은 자릿수를 왼편으로 회전하고

R은 자릿수를 오른편으로 회전하는 명령어인데

 

나는 만약 n이 3자리 이면

3자리에서 오른쪽, 왼쪽으로 회전하는 줄 알았다.

n = 123이면 L = 231 , R = 312  이렇게 말이다.

하지만 문제는 무조건 네 자리 가정이었다..

n = 123이면 L = 1230 , R = 3210 이런 식으로 말이다.

 

문제에 3자리나 2자리 예제가 없어서 헷갈렸다..

문제를 이해하는 능력이 부족한 것 같다.. 더 많이 풀어보면 해결될 거라 믿고 있다..

 

명령어 나열을 하는 부분을 구현하는 방법은 다양한데

나는 그냥 String배열을 ""로 초기화하고

S면 +=S, L이면 +=L 이런 식으로

큐에 넣고 전의 것에 +=명령어를 해주었다.

나는 이 방식이 익숙하고 편하다..

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Q9019 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int tc = scan.nextInt();
        
        while(tc-- > 0) {
            int n = scan.nextInt();
            int m = scan.nextInt();
            String [] command = new String[10000];
            boolean [] visited = new boolean[10000];
            Queue<Integer> q = new LinkedList<>();
            
            visited[n] = true;
            q.add(n);
            Arrays.fill(command, "");
            
            while(!q.isEmpty() && !visited[m]) {
                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;    
                
                System.out.println(L+" "+R);
                if(!visited[D]) {
                    q.add(D);
                    visited[D] = true;
                    command[D] = command[now]+"D";
                }
                if(!visited[S]) {
                    q.add(S);
                    visited[S] = true;
                    command[S] = command[now]+"S";
                }
                if(!visited[L]) {
                    q.add(L);
                    visited[L] = true;
                    command[L] = command[now]+"L";
                }
                if(!visited[R]) {
                    q.add(R);
                    visited[R] = true;
                    command[R] = command[now]+"R";
                }
            }
            System.out.println(command[m]);
        }
    }
 
}