[Java] 백준 9019.DSLR

문제

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

9019번: DSLR

풀이

문제에서 주어진 것들을 적용하여 풀이하는 문제. 

 L 메소드 ( 왼쪽으로 쉬프트 ) 를 잘못 구현하여서 틀렸다.

내가 구현한 코드

    int L(int n){
        if(n ==0 )return 0;
        int temp = n;
        temp *= 10;
        if(temp /limit >= 1){
            temp = (temp/limit) % limit;
        }
        n = temp;
        return n;
    }

이때 limit은 10000이다.

잘 돌아가는 것 같지만 L(1023)을 입력하면, output 은 0231 가 되야 한다.

10230 -> 1 % 10000 -> 1 이 리턴되는 잘못된 코드다.

 

또한 각 테스트 케이스마다 큐 방문 처리를 해줄 배열을 초기화를 안했다.

 

아래는 BFS를 사용한 정답 코드이다. 

각 코드에서 , 큐에 삽입 하기 전에 방문 처리를 해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            sb.append(BFS(A, B)).append("\n");
        }
        System.out.println(sb);
    }

    public static String BFS(int A, int B) {
        Queue<Pair<Integer, String>> queue = new LinkedList<>();
        boolean[] check = new boolean[10000];
        check[A] = true;
        queue.add(new Pair(A, ""));
        while (!queue.isEmpty()) {
            Pair<Integer, String> p = queue.poll();
            int n = p.getKey();
            String pro = p.getValue();
            if (n == B) {
                return pro;
            }
            // D
            int nn = n * 2;
            if (nn > 9999) {
                nn %= 10000;
            }
            if (!check[nn]) {
                check[nn] = true;
                queue.add(new Pair(nn, pro + "D"));
            }
            // S
            nn = n - 1;
            if (nn < 0) {
                nn = 9999;
            }
            if (!check[nn]) {
                check[nn] = true;
                queue.add(new Pair(nn, pro + "S"));
            }
            // L
            nn = ((n % 1000) * 10) + (n / 1000);
            if (!check[nn]) {
                check[nn] = true;
                queue.add(new Pair(nn, pro + "L"));
            }
            // R
            nn = ((n % 10) * 1000) + (n / 10);
            if (!check[nn]) {
                check[nn] = true;
                queue.add(new Pair(nn, pro + "R"));
            }
        }
        return "";
    }
}