[백준] 9019 - DSLR JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

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 10000으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S는는 n에서 1 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 L을 적용하면 2341 이 되고 R 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 LL이나 RR RR을 출력해야 한다.

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

입력
프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T T는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A와와 B는 모두 0 이상 10,000 미만이다.

출력
A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러 가지면,, 아무거나 출력한다.

접근방법

 3일째 의도하지 않게 같은 유형의 문제를 푸는 기분이다. A가 각 계산을 통해 B로 변환되는 최소의 명령어를 출력하는 문제이다. A가 D, S, L, R로 변환하는 것을 각 노드라고 본다면, A는 한 번에 4가지 노드로 뻗어나갈 수 있으며, B까지 도달하는 가장 짧은 경로를 찾는 탐색의 문제로 귀결된다. 그래프 탐색에 대한 생각을 가지고 풀이로 접근하자. 

풀이

 그래프 완전 탐색에는 대표적으로 DFS와 BFS가 있다. 단, 해당 문제에서는 반드시 BFS를 써야 한다. 문제를 많이 풀다 보니, 자연스럽게 체득되었지만, 이유를 생각해보면 다음과 같다.

 

DFS는 최소를 보장할 수 없다.

 DFS는 한 방향에서 갈 수 있는 리프 노드를 찍고 나서야 반환을 수행한다. A와 B사이에 얼마나 많은 노드를 거쳐야 하는지 알 수 없고, 찾았다 한들 그것이 최소라는 보장이 없다. 운 좋게 타깃 노드 B에 도착하면 좋겠지만, 도착하지 않았다면 해당 문제에서는 10000개의 공간을 다 탐색하고 나서야 첫번째 방향에 대한 탐색이 끝날 수도 있다.(극단적으로 시간이 오래 걸린다는 얘기이다.) 중간에 노드를 찾았다고 해도 모든 노드로 탐색하여 B에 도달하는 방법 중에 가장 작은 값을 찾아야한다. 

 

BFS는 그럼 최소를 보장하는가? 

 보장할 수 있다. 모든 깊이(Depths) 마다 확인을 하기 때문에 가장 적은 깊이에서 찾아낸 타겟노드 B가 A에서 갈 수 있는 최단 경로가 된다. 

 

해당 문제와 같이 A에서 B로 가야 하나, A와 B 간의 연결성을 명시해주지 않는 경우, 이와 같이 BFS를 통해 동적으로 값을 찾을 수 있다는 것을 인지하자. 

 

실패 원인

 BFS를 통한 전반적인 이론에는 통과했지만, 수많은 시간 초과와 실패를 겪었다. 처음에는 문자 로테이션을 해야 하는 부분이 있어서 데이터를 숫자로 받지 않고 문자로 받은 뒤, 해당 명령들을 처리했다. 돌아봐서 생각하는 거지만, 당연히 숫자로 계산하는 것이 빠르다.(자릿수가 고정되어있기에 더욱 그렇다.) 1차적인 시간 초과 문제는 여기에서 일어났다.

 

 다음 문제는 나는 결괏값을 저장하기 위해 Pair 클래스를 만들어 사용했고, 방문 확인을 위해 HashMap을 이용했다. 고정된 테이블을 만드는 것보다 동적으로 만드는 것이 더 효율적이라고 생각했기 때문이다. 내가 생각할 수 있는 모든 경우의 수로 값을 대입하여, 테스트를 진행하였으나 틀린 점을 못 찾았는데... 아무래도 반례가 있는 것 같다. -_-;

 

결국 고정 배열 두 개를 써서, 하나는 방문 확인을 위해 사용했고, 나머지 하나는 명령어를 순차적으로 담기 위해 사용했다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk ;
        int cnt = Integer.parseInt(br.readLine());

        for (int i  = 0 ; i < cnt ; i ++){
            stk = new StringTokenizer(br.readLine()," ");
            String start = stk.nextToken();
            String target = stk.nextToken();
            sb.append(solution(Integer.parseInt(start),Integer.parseInt(target))).append("\n");
        }

        System.out.println(sb);

    }


    

    private String solution(int start,int target) {

        Queue<Integer> queue = new LinkedList<>();
        String[] result = new String[100000];
        boolean[] visit = new boolean[100000];
        //초기값 
        queue.add(start);
        visit[start] =true;
        result[start] = "";

        while(!queue.isEmpty()){

            int cur_data = queue.poll();
            if(cur_data == target){
                break;
            }

            for (int i = 0 ; i < 4;i++){
                int next_data = doDSLR(i,cur_data);
                if(!visit[next_data]){
                    visit[next_data] = true;
                    queue.add(next_data);
                    //데이터 누적
                    result[next_data] = result[cur_data] + indexor(i);
                }
            }

        }


        return result[target];
    }

    private int doDSLR(int way,int data){

        int result = 0;
        switch (way){
            case 0:
                //2배로 늘리고 9999 초과과이면 10000으로 나눔
                result = (2*data)%10000;
                break;
            case 1:
                // n -1 을 저장 n= 0이라면 9999대신 저장

                result = data == 0 ? 9999: data-1;
                break;
            case 2:
                //왼쪽 시프트 로테이션
                int temp3 = (data/1000);
                result = data%1000*10 +temp3 ;
                break;
            case 3:
                //오른쪽 시프트 로테이션
                int temp4 = data%10;
                result = temp4*1000+data/10;
                break;
        }

        return result;

    }


    private String indexor(int i){
        String result ="";
        switch (i){
            case 0:
                result = "D";
                break;
            case 1:
                result = "S";
                break;
            case 2:
                result = "L";
                break;
            case 3:
                result = "R";
                break;

        }
        return result;
    }


}

결과

 

 

 문제를 보자마자. 풀 수 있는 로직이 보였는데, 구현하는 과정에서 아직도 실력이 부족함을 느낀다.  사실 코딩 테스트에서는 빠르고 정확한 게 장땡인데, 여전히 주어진 조건으로 고정 배열을 쓰는 것이 뭔가 껄끄럽다.(껄끄러우면 잘하기라도 해야 하는데 그것도 아니다 ㅠㅠㅠㅠ) 깝죽거리지 말고... 문제를 풀 수 있는 가장 빠른 방법으로 해결한 뒤, 욕심이 나면 그때 변경하는 방식으로 진행하는 것이 더 중요하다고 생각한다. 알고도 틀리고, 수정하는데 이렇게 시간낭비 말자.  

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.