[백준] no9019: DSLR

문제

주어진 숫자 A에서 B가 되도록, DSLR에 맞는 연산을 반복하고, 최소한의 연산을 수행했을 경우의 DSLR조합을 출력

 

문제 링크 : https://www.acmicpc.net/problem/9019

---

원리

BFS 사용

 * D: n을 두 배로 바꾼다. 결과 값이 9999보다 큰 경우에는 10000으로 나눈 나머지를 취한다.
 * S: n에서 1을 뺀 결과를 저장. n이 0이라며느 9999저장
 * L: n의 각 자릿수를 왼편으로 회전시켜 저장
 * R: n의 각 자릿수를 오른편으로 회전시켜 저장
 * A와 B가 주어질 때, 가장 빠른 연산방법 구하기 = 탐색 (4가지 모두 해보고 카운트 저장하는 방식)
 * 단, 0100 1000 등 0이 들어있는 경우, 0001 = 1 같이 되기때문에 조심
 *
 * BFS로 탐색 하다가, B와 일치하는 연산결과가 나오면 반복 중지(최소값)
 * 객체에는 연산방법(String), 연산 결과(String) 필요

---

풀이방법

1. Integer사용 [런타임 에러 (NumberFormat) 발생]

 

---

나의 코드

1. 런타임 에러 (NumberFormat) 발생 + 메모리 초과

: Integer로 계산하니 NumberFormat 발생. Integer 범위를 벗어나사 발생하므로 BigInteger로 변경했다.

: 하지만, BigInteger를 사용해도 메모리 초과가 발생.

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 i=0; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        String A = st.nextToken();
        int B = Integer.parseInt(st.nextToken());

        if(A.length()!=4) {
            String temp = "";
            for(int j=0; j<4-A.length(); j++) temp += "0";
            A = temp + A;
        }
        System.out.println(Integer.parseInt(A));
        String result = BFS(A, B);
        bw.write(result+"\n");
    }
    bw.close();
}

/**
 * 탐색용 메소드
 */
private static String BFS(String A, int B) {
    String answer = "";
    Deque<Register> dq = new ArrayDeque<>();
    dq.add(new Register(A, ""));

    while(!dq.isEmpty()) {
        Register now = dq.poll();
        int checkRec = Integer.parseInt(now.Record);
        if(checkRec==B) {
            answer = now.DSLR;
            break;
        }
        for(int i=0; i<4;i++) {
            if(i==0) dq.add( D(now) );
            else if (i==1) dq.add( S(now) );
            else if (i==2) dq.add( L(now) );
            else dq.add( R(now) );
        }
    }

    return answer;
}

/**
 * 탐색을 위해 값을 저장하는 레지스터 객체클래스
 */
private static class Register {
    private String Record;
    private String DSLR;
    public Register(String record, String dslr) {
        this.Record = record;
        this. DSLR = dslr;
    }
}

/**
 * 이 아래로는 DSLR 각각의 연산을 담당하는 메소드들 (BFS에서 순차적으로 호출)
 */
private static Register D (Register register) {
    String record = register.Record;
    int intRec = Integer.parseInt(record)*2;
    String dslr = register.DSLR + "D";
    if(intRec>9999) record = String.valueOf(intRec%10000);
    else record = String.valueOf(intRec);

    if(record.length()!=4) {
        String temp = "";
        for(int i = 0 ; i<4-record.length() ; i++) temp += "0";
        record = temp + record;
    }

    return new Register(record, dslr);
}

private static Register S (Register register) {
    String record = register.Record;
    int intRec = Integer.parseInt(record) - 1;
    String dslr = register.DSLR + "S";
    if(intRec==0) record = "9999";
    else record = String.valueOf(intRec);

    if(record.length()!=4) {
        String temp = "";
        for(int i = 0 ; i<4-record.length() ; i++) temp += "0";
        record = temp + record;
    }

    return new Register(record, dslr);
}

private static Register L (Register register) {
    String record = register.Record;
    String modifyRecord = record.substring(1,4) + record.charAt(0);
    String dslr = register.DSLR + "L";
    return new Register(modifyRecord, dslr);
}

private static Register R (Register register) {
    String record = register.Record;
    String modifyRecord = record.charAt(3) + record.substring(0,4);
    String dslr = register.DSLR + "R";
    return new Register(modifyRecord, dslr);
}

 

2. 시간초과

: BigInteger를 이용해 다른 방식으로 구현해보았으나, 시간초과 발생. 예시문제와도 다른 결과가 발생한다.

: BigInteger변환과정에서 문제가 발생한 듯 하다.

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 i=0; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        BigInteger A = new BigInteger(st.nextToken());
        BigInteger B = new BigInteger(st.nextToken());

        String result = BFS(A, B);
        bw.write(result+"\n");
    }
    bw.close();
}

/**
 * 탐색용 메소드
 */
private static String BFS(BigInteger A, BigInteger B) {
    Deque<BigInteger> dq = new ArrayDeque<>();
    boolean[] visited = new boolean[100000]; //방문 체크 배열
    String[] cmd = new String[100000]; // 명령어를 담는 배열

    dq.add(A);
    visited[A.intValue()] = true;
    Arrays.fill(cmd, ""); // 배열을 초기화. 안하면 null 값으로 채워지게 됨

    while(!dq.isEmpty() && !visited[B.intValue()]) {
        BigInteger now = dq.poll();

        BigInteger D = (now.multiply(BigInteger.valueOf(2))).mod(BigInteger.valueOf(10000)); //
        BigInteger S = now.compareTo(BigInteger.valueOf(0))==0? BigInteger.valueOf(9999) : now.subtract(BigInteger.valueOf(1));
        BigInteger L = (now.mod(BigInteger.valueOf(1000)))
                .multiply(BigInteger.valueOf(10))
                .add(now).divide(BigInteger.valueOf(1000));
        BigInteger R = (now.mod(BigInteger.valueOf(10)))
                .multiply(BigInteger.valueOf(1000))
                .add(now).divide(BigInteger.valueOf(10));

        if(!visited[D.intValue()]) {
            dq.add(D);
            visited[D.intValue()] = true;
            cmd[D.intValue()] = cmd[now.intValue()] + "D";
        }

        if(!visited[S.intValue()]) {
            dq.add(S);
            visited[S.intValue()] = true;
            cmd[S.intValue()] = cmd[now.intValue()] + "S";
        }

        if(!visited[L.intValue()]) {
            dq.add(L);
            visited[L.intValue()] = true;
            cmd[L.intValue()] = cmd[now.intValue()] + "L";
        }

        if(!visited[R.intValue()]) {
            dq.add(R);
            visited[R.intValue()] = true;
            cmd[R.intValue()] = cmd[now.intValue()] + "R";
        }
    }
    return cmd[B.intValue()];
}

---

레퍼런스 코드

Int를 사용한 코드 : 링크

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 i=0; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        String result = BFS(A, B);
        bw.write(result+"\n");
    }
    bw.close();
}

/**
 * 탐색용 메소드
 */
private static String BFS(int A, int B) {
    Deque<Integer> dq = new ArrayDeque<>();
    boolean[] visited = new boolean[100000]; //방문 체크 배열
    String[] cmd = new String[100000]; // 명령어를 담는 배열

    dq.add(A);
    visited[A] = true;
    Arrays.fill(cmd, ""); // 배열을 초기화. 안하면 null 값으로 채워지게 됨

    while(!dq.isEmpty() && !visited[B]) {
        int now = dq.poll();

        int D = now * 2 % 10000;
        int S = now==0 ? 9999 : now-1;
        int L = (now%1000)*10 + now/1000;
        int R = (now%10)*1000 + now/10;
        if(!visited[D]) {
            dq.add(D);
            visited[D] = true;
            cmd[D] = cmd[now] + "D";
        }

        if(!visited[S]) {
            dq.add(S);
            visited[S] = true;
            cmd[S] = cmd[now] + "S";
        }

        if(!visited[L]) {
            dq.add(L);
            visited[L] = true;
            cmd[L] = cmd[now] + "L";
        }

        if(!visited[R]) {
            dq.add(R);
            visited[R] = true;
            cmd[R] = cmd[now] + "R";
        }
    }
    return cmd[B];
}