[백준] DSLR : 9019 : Java - BFS, 최단 거리 (G4)

1. 💎 문제

9019번: DSLR

• 4개의 명령으로 A에서 B를 만들 수 있는 최소한의 명령어의 나열을 구한다.
• 나열이 여러가지면, 아무거나 출력한다. 
• D : D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다.
• S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
• L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
• R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

---

 

 

2. 🤔 어떻게 풀까 

방법1. 우선 D, S명령으로만 B와 같은 숫자의 조합을 만든다

어떻게 하면 최소한의 명령으로 B를 만들 수 있을까? 고민했을 때 우선, D와 S 명령어만 사용하여 B의 숫자 조합과 일치하는 수로 만들기로 했다. 무슨 말이냐면 B가 1234라고 했을 때 2341, 3412, 4123 등 숫자를 찾는 것이다. 그러면 L과 R연산을 하면 바로 B를 만들 수 있기에 생각했지만, 도저히 어떻게 구현할지를 모르겠었다.

 

D와 S 명령어만 이용하여 수들의 조합을 만들 때, 탐색의 끝이 언제인지를 정의할 수 없었다. 해당 문제는 최소길이를 보장해야 하는데, 현재 탐색된 길이가 최소한의 길이인지 판단할 수 있는 기준이 없었다.

 

방법 2. BFS로 완전 탐색

결국 알고리즘 분류로 힌트를 봤다! 이 문제는 BFS로 완전 탐색을 이용한 문제였다. 시간제한이 6초로 다른 문제들에 비해 매우 긴 편으로 모든 요소들을 전체 탐색해도 된다. 다시 BFS로 구현하면 되는 힌트를 얻고 구현해봤다. 하지만 많은 실패를.. 겪었다.

 

 

질문 게시판에 있는 여러 반례들을 확인하며 내 코드가 무엇이 문제인지 찾았다.

가장 큰 이유는 L과 R의 연산 과정에 있었다. 바로 L과 R연산을 하면 무조건 4자리가 되어야한다!!! 123을 R연산하면 312가 되는 것이 아니고 3012가 되야한다.. 호올리. 아마 이 조건 때문에 이 문제의 정답률이 엄청 낮은 것 같다.

 

 

문제. String 연산은 많은 시간 소모

이제 대부분의 반례들이 통과 되는 것을 확인하고 제출했지만 시간초과가 났다... 아마 숫자 연산을 하는 과정에서 모두 String을 이용하여 연산을 했는데 여기가 문제인 것 같았다. 그리고 뭔가 복잡하다!!

                else if(i==2){
                    // 3. R
                    String str =  Integer.toString(current.pos);

                    String exLastStr = str.substring(0, str.length()-1);
                    while(exLastStr.length() != 3){
                        exLastStr = "0"+exLastStr;
                    }
                    String lastStr = str.substring(str.length()-1);
                    nextPos = Integer.parseInt(lastStr + exLastStr)%10000;

                    nextCommand = current.command + "R";
                }
                else if(i==3){
                    // 3. L1
                    String str =  Integer.toString(current.pos);
                    if(str.length() == 1){
                        nextPos =  Integer.parseInt(str +"0");
                    }else{
                        String exFirstStr = str.substring(1, str.length());
                        String FirstStr = String.valueOf(str.charAt(0));

                        if(str.length() == 4){
                            nextPos = Integer.parseInt(exFirstStr + FirstStr)%10000;
                        } else{
                            nextPos = Integer.parseInt(FirstStr + exFirstStr)%10000;
                        }
                    }
                    nextCommand = current.command + "L";
                }

 

해결. Int로 연산

L과 R연산을 대체 어떻게 수식으로 표현하는지 모르겠었는데, 역시 방법은 있었다. 훨씬 간결하다😅

우선 R연산은 오른쪽으로 수를 이동시켜야 하므로 전체 수에서 / 10을 하여 오른쪽으로 이동한다. 예를 들어 숫자가 1234일 때, 나누기 10을 하여 123을 만들고, 1234을 10으로 나누었을 때의 나머지를 구하여 4를 알아낸다. 그리고 1000을 곱하여 4000 만들어 더한다.

 nextPos = 4000 + 123 = 4123

세 자리인 234를 계산해보면, 4000+ 23 = 4023이 된다. 네자리 수를 보장하기에 가능하다. L연산도 마찬가지이다.

                else if(i==2){
                    // 3. R
                    nextPos = (current.pos%10)*1000 + current.pos/10;
                    nextCommand = current.command + "R";
                }
                else if(i==3){
                    // 4. L1
                    nextPos = (current.pos/1000) + (current.pos%1000)*10;
                    nextCommand = current.command + "L";
                }

 

 

3. 🖥️  코드

한 위치에 대해 4가지 연산을 적용한 모든 경우를 큐에 넣어 BFS 탐색을 이어간다.  큐에 넣은 위치는 `isVisited = ture`로 방문 표시를 해준다. 이때 최초로 B가 만들어졌을 때 가장 최소한의 명령어가 되므로 바로 리턴하여 결과를 출력한다.

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

public class Main {

    public static String ans;
    public static boolean [] isVisited;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for(int t=0; t<T; t++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int [] countMap = new int[10001];
            isVisited = new boolean[10001];
            Arrays.fill(countMap, Integer.MAX_VALUE);
            BFS(A,B, countMap);
            bw.write(ans+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void BFS(int a, int b, int[] countMap) {
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(a,""));
        countMap[a] = 0;

        while(!que.isEmpty()){
            Point current = que.poll();
            if(current.pos == b){
                ans = current.command;
                return;
            }
            // 4가지 연산
            for(int i=0; i<4; i++){
                int nextPos = 0;
                String nextCommand = null;
                if(i==0){
                    //1. D
                    nextPos = (current.pos*2)%10000;
                    nextCommand = current.command + "D";
                }
                else if(i ==1){
                    // 2. S
                    nextPos = current.pos-1;
                    nextCommand = current.command + "S";
                    if(nextPos <0)
                        nextPos = 9999;
                }
                else if(i==2){
                    // 3. R
                    nextPos = (current.pos%10)*1000 + current.pos/10;
                    nextCommand = current.command + "R";
                }
                else if(i==3){
                    // 4. L1
                    nextPos = (current.pos/1000) + (current.pos%1000)*10;
                    nextCommand = current.command + "L";
                }

                if(!isVisited[nextPos]){
                    que.add(new Point(nextPos,nextCommand));
                    isVisited[nextPos] = true;
                }
            }
        }
    }
}

class Point{
    int pos;
    String command;

    public Point(int pos, String command){
        this.pos = pos;
        this.command =command;
    }
}