[BOJ] 9019 DSLR - JAVA

1. 문제

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

---

2. 풀이

TC 수에 맞춰서 A,B를 입력받고 경로길이 배열 dp를 완성시킨다.

그 후 dp[B]부터 역순으로 경로를 찾아낸다.

Main

A,B를 입력받고 count 메서드를 호출한다.

그 후 find의 반환값을 sb에 더한다.

static int[] dp;
static int MAX = 10000;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();
   for(int tc=0;tc<T;tc++){
      StringTokenizer st = new StringTokenizer(in.readLine());
      int A = Integer.parseInt(st.nextToken());
      int B = Integer.parseInt(st.nextToken());

      count(A,B);
      sb.append(find(B));

   }
   System.out.print(sb);
}

 

BFS

dp를 10001로 채우고 dp[A]에 0을 저장한 뒤 시작한다.

현재 num에서 다음 수로 갈 수 있는 방법은 네 가지다.

D : num*2%10000

S : (num+10000-1)%10000. num-1이 음수가 되면 안되므로 (num+10000-1)%MAX로 구한다.

L : (num%1000)*10 + num/1000

R : (num%10)*1000+(num/10)

 

dp[next]가 10001이라면 방문한 적 없는 것이므로 dp[next]에 dp[num]+1을 저장한 뒤 queue에 추가한다.

public static void count(int A, int B){
   dp = new int[MAX];
   Arrays.fill(dp,10001);
   dp[A] = 0;
   Queue<Integer> queue = new ArrayDeque<>();
   queue.offer(A);

   int num, next;
   while(!queue.isEmpty()){
      num = queue.poll();
      if(num==B) break;

      for(int i=0;i<4;i++){
         //DSLR순서
         if(i==0) next = (num*2) % MAX;
         else if(i==1) next = (num+ MAX -1)% MAX;
         else if(i==2) next = (num%1000)*10 + num/1000;
         else next = (num%10)*1000 + (num/10);

         if(next >= 0 && next < MAX && dp[next] == MAX+1){
            dp[next] = dp[num]+1;
            queue.offer(next);
         }
      }

   }
}

 

경로찾기

dp[B]부터 갈 수 있는 숫자를 역순으로 구하되, 1 작은 숫자로만 이동한다.

이 때 주의해야할 점은 D연산은 %10000 때문에 35 -> 70, 5035 -> 70 두 가지 경우가 가능하다는 것이다.

그래서 D연산 역순은 num/2, (num+10000)/2 두 가지로 체크했다. 

S연산은 num+1을 %10000한다.

L,R은 위와 반대로 바꾸면 된다.

만약 dp[next] == dp[num]-1이라면 이동할 수 있는 것이므로 num을 next로 교체하고 answer[idx]에 연산이름을 저장한다.

 

StringBuilder를 하나 만들어서 answer의 역순으로 추가한다.

public static String find(int B){
   //끝에서부터 1 차이 나는 걸로 알아내기
   char[] comm = {'D','D','S','R','L'};
   char[] answer = new char[dp[B]];
   int num = B, next;
   for(int idx=0;idx<dp[B];idx++){
      //4가지 경우 찾고 저장, DDSRL순서
      for(int i=0;i<5;i++){
         if(i==0 && num%2 == 0) next = (num/2)% MAX;
         else if(i == 1 && num%2 == 0) next = (num+10000)/2%MAX;
         else if(i==2) next = (num+1)% MAX;
         else if(i==3) next = (num%1000)*10 + num/1000;
         else if(i==4) next = (num%10)*1000 + (num/10);
         else continue;

         if(next < MAX && dp[next] == dp[num]-1){
            num = next;
            answer[idx] = comm[i];
            break;
         }
      }
   }

   StringBuilder sb = new StringBuilder();
   for(int i=dp[B]-1;i>=0;i--){
      sb.append(answer[i]);
   }

   return sb.append('\n').toString();
}

 

전체 코드

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

public class BOJ_9019_DSLR {
   static int[] dp;
   static int MAX = 10000;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      for(int tc=0;tc<T;tc++){
         StringTokenizer st = new StringTokenizer(in.readLine());
         int A = Integer.parseInt(st.nextToken());
         int B = Integer.parseInt(st.nextToken());

         count(A,B);
         sb.append(find(B));

      }
      System.out.print(sb);
   }

   public static void count(int A, int B){
      dp = new int[MAX];
      Arrays.fill(dp,10001);
      dp[A] = 0;
      Queue<Integer> queue = new ArrayDeque<>();
      queue.offer(A);

      int num, next;
      while(!queue.isEmpty()){
         num = queue.poll();
         if(num==B) break;

         for(int i=0;i<4;i++){
            //DSLR순서
            if(i==0) next = (num*2) % MAX;
            else if(i==1) next = (num+ MAX -1)% MAX;
            else if(i==2) next = (num%1000)*10 + num/1000;
            else next = (num%10)*1000 + (num/10);

            if(next >= 0 && next < MAX && dp[next] == MAX+1){
               dp[next] = dp[num]+1;
               queue.offer(next);
            }
         }

      }
   }

   public static String find(int B){
      //끝에서부터 1 차이 나는 걸로 알아내기
      char[] comm = {'D','D','S','R','L'};
      char[] answer = new char[dp[B]];
      int num = B, next;
      for(int idx=0;idx<dp[B];idx++){
         //4가지 경우 찾고 저장, DDSRL순서
         for(int i=0;i<5;i++){
            if(i==0 && num%2 == 0) next = (num/2)% MAX;
            else if(i == 1 && num%2 == 0) next = (num+10000)/2%MAX;
            else if(i==2) next = (num+1)% MAX;
            else if(i==3) next = (num%1000)*10 + num/1000;
            else if(i==4) next = (num%10)*1000 + (num/10);
            else continue;

            if(next < MAX && dp[next] == dp[num]-1){
               num = next;
               answer[idx] = comm[i];
               break;
            }
         }
      }

      StringBuilder sb = new StringBuilder();
      for(int i=dp[B]-1;i>=0;i--){
         sb.append(answer[i]);
      }

      return sb.append('\n').toString();
   }
}

---

3. 결과

bfs로 짧은 거리를 알아내고 역순으로 경로를 알아낸다는 아이디어까지는 좋았지만, %10000연산때문에 생긴 고려할 부분을 빨리 캐치하지 못했다. (/2, *2)