[BOJ] 9019. DSLR(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

주어진 명령어에 맞게 가능한 모든 경우의 수로 동작시키면 된다.

D : 2n mod 10000

S : n-1을 레지스터에 저장. n이 0 이라면 9999 가 대신 레지스터에 저장

L : n의 각 자릿수를 왼편으로 회전. d2, d3, d4, d1

R : n의 각 자릿수를 오른편으로 회전. d4, d1, d2, d3

#. Code

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 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
 
            String res = process(A, B);
            sb.append(res + "\n");
        }
 
        System.out.println(sb);
    }
 
    static String[] oper = {"D", "S", "L", "R"};
    private static String process(int A, int B) {
 
        Queue<Info> q = new LinkedList<>();
        boolean[] checked = new boolean[10000];
        q.add(new Info(A, ""));
        
        while(!q.isEmpty()) {
            
            Info now = q.poll();
            if(now.n == B) return now.comd;
            
            for (int i = 0; i < 4; i++) {
                int res = command(now, i);
                
                if(!checked[res]) {
                    checked[res] = true;
                    q.add(new Info(res, now.comd + oper[i]));
                }
            }
        }
        
        return "";
    }
 
    private static int command(Info now, int comd) {
        
        switch(comd) {
        // D 는 n을 두 배로
        case 0: return (now.n * 2) % 10000;
        // S 는 n에서 1 을 뺀 결과. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
        case 1: return now.n == 0 ? 9999 : now.n - 1;
        // L 은 n의 각 자릿수를 왼편으로 회전(d2, d3, d4, d1)
        case 2: return (now.n % 1000) * 10 + (now.n / 1000);
        // R 은 n의 각 자릿수를 오른편으로 회전(d4, d1, d2, d3)
        case 3: return (now.n % 10) * 1000 + (now.n / 10);
        }
        
        return 0;
    }
 
    static class Info {
        int n;
        String comd;
        
        public Info(int n, String comd) {
            this.n = n;
            this.comd = comd;
        }
 
    }
}
 

#. Code_v2

기존 해결 방법에서는

Queue에서 객체를 다룬 점과 String 객체를 계속해서 생성하다 보니 실행 시간이 오래 걸렸던 것 같다.

두 번째 방법에서는

1. 확인한 숫자 상태를 저장하는 checked boolean 배열

2. 특정 숫자가 만들어질 때 어떤 명령을 사용했는지를 저장하는 operations char 배열

3. 특정 숫자가 만들어지기 전 어떤 숫자였는지를 저장하는 before int 배열

을 사용하였다.

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_v2 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
 
            sb.append(process(A, B) + "\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static char[] oper = {'D', 'S', 'L', 'R'};
    private static StringBuilder process(int A, int B) {
 
        boolean[] checked = new boolean[10000];
        char[] operations = new char[10000];
        int[] before = new int[10000];
        Queue<Integer> q = new LinkedList<>();
        
        q.add(A);
        
        while(!q.isEmpty()) {
            
            int now = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int res = command(now, i);
                // 이미 확인한 숫자가 아닐 경우
                if(!checked[res]) {
                    checked[res] = true; // 방문 체크
                    q.add(res); // 큐에 추가
                    before[res] = now; // 현재 결과 index에 명령을 수행하기 전 숫자를 저장
                    operations[res] = oper[i]; // 현재 결과 index에 어떤 명령을 수행했는지 저장
                }
                // 숫자 B가 만들어졌을 경우
                if(res == B) {
                    int tmp = B;
                    StringBuilder sb = new StringBuilder();
                    // before 배열에 저장된 operation 값을 tracking
                    while(tmp != A) {
                        sb.insert(0, operations[tmp]);
                        tmp = before[tmp];
                    }
                    
                    return sb;
                }
            }
        }
        
        return null;
    }
 
    private static int command(int now, int comd) {
        
        switch(comd) {
        // D 는 n을 두 배로
        case 0: return (now * 2) % 10000;
        // S 는 n에서 1 을 뺀 결과. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
        case 1: return now == 0 ? 9999 : now - 1;
        // L 은 n의 각 자릿수를 왼편으로 회전(d2, d3, d4, d1)
        case 2: return (now % 1000) * 10 + (now / 1000);
        // R 은 n의 각 자릿수를 오른편으로 회전(d4, d1, d2, d3)
        case 3: return (now % 10) * 1000 + (now / 10);
        }
        
        return 0;
    }
 
}
 

line 45~50) 이미 확인한 숫자가 아닐 경우의 동작

line 52~62) 숫자 B가 만들어졌을 경우

B가 만들어지기 전 숫자, 그 전 숫자가 만들어지기 전 숫자, ... 의

명령을 tracking하면서 StringBuilder에 담고 return